※ 引述《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://webptt.com/cn.aspx?n=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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1561013445.A.E50.html