→ fmtshk: 感謝大佬詳細解說 06/20 16:35
※ 引述《fmtshk (fmtshk)》之銘言：
: https://i.imgur.com/iDPl12j.jpg
: 請問各位大神
: 這題的C,D要怎麼理解？
: 像是f(n)+o(f(n))=θ(f(n)) 這種函數跟符號相加的式子要怎麼想？
: 這樣寫可以嗎？
: https://i.imgur.com/GSi7oah.jpg
: D的[log(logn)]!比n小？ 好像是這樣，但又想說階乘比n高，這兩個如何比較？
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.10.203.208 (臺灣)
: ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1560153264.A.089.html
: ※ 編輯: fmtshk (111.241.215.192 臺灣), 06/10/2019 16:01:13
: 推 Aa841018: 出現o(f(n))就表示時間複雜度最小也比f(n)來的大！ 06/10 16:23
C的部分應該是定義
o(f(n))：f(n)<c*g(n)
Θ定義：c0*g(n)≦f(n)≦c1*g(n)
那用c*g(n)取代o(f(n))代回原式
f(n)+o(f(n))→f(n)+c*g(n)
再套Θ定義
→(c0+c)g(n)≦f(n)+c*g(n)≦(c1+c)g(n)
所以等於Θ(n)
D的部分要比就拆開來看
[log(logn)]!
=log(logn)*[log(logn)-1]*[log(logn)-2]*...*[log(logn)-(log(logn)-1)]
加入比大小概念
<log(logn)*log(logn)*log(logn)*...
這串log(logn)乘起來比[log(logn)]!大也仍然是對數類別
小於多項式類別，所以等於O(n)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.164.13.34 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1561013445.A.E50.html