[理工] (log(logn))!的時間複雜度
題目：(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
推
11/09 00:42,
5年前
, 1F
11/09 00:42, 1F
假如我要拿來跟n比大小就會有問題
<法一>loglogn logloglogn < O(n)
<法二>n logloglogn > O(n)
另請問 如果這題要找theta 要怎麼算？
※ 編輯: cschenptt (114.136.20.232), 11/09/2018 00:52:45
推
11/09 00:50,
5年前
, 2F
11/09 00:50, 2F
→
11/09 00:52,
5年前
, 3F
11/09 00:52, 3F
→
11/09 00:52,
5年前
, 4F
11/09 00:52, 4F
推
11/09 01:27,
5年前
, 5F
11/09 01:27, 5F
→
11/09 01:28,
5年前
, 6F
11/09 01:28, 6F
→
11/09 01:28,
5年前
, 7F
11/09 01:28, 7F
→
11/09 01:28,
5年前
, 8F
11/09 01:28, 8F
推
11/09 01:31,
5年前
, 9F
11/09 01:31, 9F
→
11/09 01:31,
5年前
, 10F
11/09 01:31, 10F
感謝大大 原來是這邊錯了 這樣的話會有loglogn項
所以<法二>由n logloglogn
修改為->loglogn logloglogn 就跟<法一>一樣了
感謝
推
11/09 01:37,
5年前
, 11F
11/09 01:37, 11F
→
11/09 01:37,
5年前
, 12F
11/09 01:37, 12F
→
11/09 01:37,
5年前
, 13F
11/09 01:37, 13F
※ 編輯: cschenptt (223.137.49.170), 11/09/2018 23:16:57
推
11/09 23:45,
5年前
, 14F
11/09 23:45, 14F
→
11/09 23:45,
5年前
, 15F
11/09 23:45, 15F
→
11/09 23:45,
5年前
, 16F
11/09 23:45, 16F