作者cschenptt (chen)
看板Grad-ProbAsk
标题[理工] (log(logn))!的时间复杂度
时间Fri Nov 9 00:39:58 2018
题目：(log(logn))!
法一
log(n!)=log(n*(n-1)*...*1)
=logn+log(n-1)+....+log(1)
<=logn+logn+...+logn (共有n项)
=n*logn ---(1)
题目取log => log((log(logn))!)
以n=(log(logn))带入上式(1)
log(n!) => log((log(logn))!)
n*logn => loglogn*logloglogn
法二
题目取log => log((log(logn))!)
log(loglogn * loglog(n-1) *....)
=logloglogn + logloglog(n-1) +....
<=logloglogn + logloglogn+...(共有n项)
=n logloglogn
请问两个方法为什麽算出来结果差这麽多
时间复杂度的等级整个不同
<法一>的答案 跟补习班一样
主要是想要问<法二>哪里不对
另外请问如果这题要用Stirling代化简
我化简不出跟<法一>一样的答案
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.136.20.232
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1541695203.A.F18.html
1F：推 wilson50101: 你取log法是拿来比大小的 不是拿来推等级的 11/09 00:42
假如我要拿来跟n比大小就会有问题
<法一>loglogn logloglogn < O(n)
<法二>n logloglogn > O(n)
另请问 如果这题要找theta 要怎麽算？
※ 编辑: cschenptt (114.136.20.232), 11/09/2018 00:52:45
3F：→ wilson50101: 应该是像图片右边这样 用Stirling应该没办法知道确切 11/09 00:52
4F：→ wilson50101: 值可是可以知道介於哪个等级之间 11/09 00:52
6F：→ skyHuan: 我自己是只有记夹挤，取log也可以用夹挤看，Stirling理 11/09 01:28
7F：→ skyHuan: 论上应该是推得出来但很容易代错，不然可以先把Stirling 11/09 01:28
8F：→ skyHuan: 的n都换成t再代你要的loglogn进去比较不会看错(? 11/09 01:28
9F：推 skyHuan: 你法二也代错了(log(logn))!=(loglogn)! 11/09 01:31
10F：→ skyHuan: =loglogn*[(loglogn)-1]*[(loglogn)-2]*..*2*1 11/09 01:31
感谢大大 原来是这边错了 这样的话会有loglogn项
所以<法二>由n logloglogn
修改为->loglogn logloglogn 就跟<法一>一样了
感谢
11F：推 skyHuan: 以上是取log後的复杂度，如果要求原本的复杂度会在对数 11/09 01:37
12F：→ skyHuan: 跟多项式之间，如下图证明(5) 11/09 01:37
※ 编辑: cschenptt (223.137.49.170), 11/09/2018 23:16:57
14F：推 wilson50101: 蛮好奇的 像是这种题目要怎麽写出他的等级 11/09 23:45
15F：→ wilson50101: 应该也只能说比什麽大或是比什麽小而已吧没办法写出 11/09 23:45
16F：→ wilson50101: 确切的等级 11/09 23:45