Re: [理工] [資結]-時間複雜度
※ 引述《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
推
11/21 10:10, , 1F
11/21 10:10, 1F
討論串 (同標題文章)