作者bernachom (Terry)
看板Grad-ProbAsk
標題[問題] complexity
時間Wed Apr 22 02:19:20 2009
請教一下
T(n)約等於，T(n/2)+c,c為constant time for 乘法運算
T(n)=O(logn)
可是..
logn不是應該為1/1+1/2+...+1/n才是嗎??
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.99.191
1F：→ s336:你一直遞回帶進去 最後T(n)=T(1)+clog(n)=O(log n) 04/22 09:46
2F：→ s336:1/1+1/2+...+1/n這是用harmonic去夾擠所求出約等於log n 04/22 09:50
3F：→ s336:T(n)=T(n/2)+c=T(n/4)+2c=.....=T(n/2^i)+ic n/2^i=1 04/22 10:08
4F：→ s336:求出i=log n 代入=>T(n)=T(1)+clog n 令T(1)=0 04/22 10:10
5F：→ bernachom:原來是這樣，謝謝您^^ 04/22 10:27
6F：→ ssccg:我覺得你對big-O的定義不太清楚，T(n) = O(logn) 04/22 20:52
7F：→ ssccg:不代表T(n)的值等於logn，而是growth rate小於等於logn 04/22 20:53
8F：→ bernachom:清楚了，謝謝您 04/24 23:28