[理工] (log(logn))!的時間複雜度

[cschenptt (chen)]

題目：(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://www.ptt.cc/bbs/Grad-ProbAsk/M.1541695203.A.F18.html
推 wilson50101: 你取log法是拿來比大小的 不是拿來推等級的
假如我要拿來跟n比大小就會有問題
<法一>loglogn logloglogn < O(n)
<法二>n logloglogn > O(n)

另請問 如果這題要找theta 要怎麼算？
※ 編輯: cschenptt (114.136.20.232), 11/09/2018 00:52:45
推 wilson50101: https://i.imgur.com/PZgLfdI.jpg
→ wilson50101: 應該是像圖片右邊這樣 用Stirling應該沒辦法知道確切
→ wilson50101: 值可是可以知道介於哪個等級之間
推 skyHuan: https://imgur.com/l9M1Fl3.jpg
→ skyHuan: 我自己是只有記夾擠，取log也可以用夾擠看，Stirling理
→ skyHuan: 論上應該是推得出來但很容易代錯，不然可以先把Stirling
→ skyHuan: 的n都換成t再代你要的loglogn進去比較不會看錯(?
推 skyHuan: 你法二也代錯了(log(logn))!=(loglogn)!
→ skyHuan: =loglogn*[(loglogn)-1]*[(loglogn)-2]*..*2*1
感謝大大 原來是這邊錯了 這樣的話會有loglogn項
所以<法二>由n logloglogn
修改為->loglogn logloglogn 就跟<法一>一樣了
感謝
推 skyHuan: 以上是取log後的複雜度，如果要求原本的複雜度會在對數
→ skyHuan: 跟多項式之間，如下圖證明(5)
→ skyHuan: https://imgur.com/WswXoUX.jpg
※ 編輯: cschenptt (223.137.49.170), 11/09/2018 23:16:57
推 wilson50101: 蠻好奇的 像是這種題目要怎麼寫出他的等級
→ wilson50101: 應該也只能說比什麼大或是比什麼小而已吧沒辦法寫出
→ wilson50101: 確切的等級