[問題] complexity

[bernachom (Terry)]

  請教一下

  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
→ s336:你一直遞回帶進去 最後T(n)=T(1)+clog(n)=O(log n)
→ s336:1/1+1/2+...+1/n這是用harmonic去夾擠所求出約等於log n
→ s336:T(n)=T(n/2)+c=T(n/4)+2c=.....=T(n/2^i)+ic     n/2^i=1
→ s336:求出i=log n 代入=>T(n)=T(1)+clog n  令T(1)=0
→ bernachom:原來是這樣，謝謝您^^
→ ssccg:我覺得你對big-O的定義不太清楚，T(n) = O(logn)
→ ssccg:不代表T(n)的值等於logn，而是growth rate小於等於logn
→ bernachom:清楚了，謝謝您