作者FRAXIS (喔喔)
看板Grad-ProbAsk
标题Re: [理工] [资结]时间复杂度
时间Sat Nov 21 00:37:38 2009
※ 引述《NOtWorThy ()》之铭言：
: 1) 3^n = 2^O(n) why is true ?
4^n = (2^2)^n = 2^2n = 2^O(n) > 3^n
: 2) 1 = o(1/n) why false ??
左右相除
: 3) show that (logn)^3 = O(n^(1/16))
左右相除，用l'Hoptial's rule
: 4) let T(n) = 4T(n/2) + n^2 / logn , T(c) = c if c < 2
递回展开
T(n) = 4T(n/2) + n^2/lg n
= 16T(n/4) + 4(n/2)^2/(lg n-1) + n^2/lg n
= n^2 (1 + 1/2 + ... 1/lgn)
= n^2 lglgn
: 以上几题有点问题
: 烦请高手不吝赐教
: 谢谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.119.162.50
1F：推 NOtWorThy:感谢~! 11/21 10:10