作者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/m.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