Re: [問題] complexity
※ 引述《bernachom (Terry)》之銘言：
: 請教一下
: T(n)約等於，T(n/2)+c,c為constant time for 乘法運算
: T(n)=O(logn)
: 可是..
: logn不是應該為1/1+1/2+...+1/n才是嗎??
: 謝謝
1. T(n) = T(n/2) + c
2. 令 f(n) = c ,使得 T(n) = aT(n/b) + f(n)
3. lg(1) 0
因為 n = n = 1 = Theta(f(n))
by master method case 2可知
T(n) = Theta( f(n)*lg n )
= Theta( c * lg n )
= Theta( lg n ) → 因為c是常數
= O( lg n )
有錯請鞭^^
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.229.77.39
討論串 (同標題文章)