推 yesa315:我覺得是O(n) n/5+7n/10 = 9n/10 < n 11/13 22:34
→ yesa315:這種樹狀的遞迴 最多只有到O(n log n ) 當每層cost為 n 時 11/13 22:36
→ yesa315:對吧!? 11/13 22:43
→ cormen5566:當a=1時，樹高不就是n了嗎? 11/15 00:30
※ 引述《sssmallwing (奄是涼小赫$__$)》之銘言：
: T(n)<= T(ceiling(n/5))+T(7n/10 +6)+O(n)
: T(n)= T(n-a)+T(a)+cn where a>=1 and c>0
: 麻煩板上各位前輩!
: 感謝大家!!
T(n) ≦ T(ceiling(n/5)) + T(7n/10 + 6) + O(n)
≒ T(n/5) + T(7n/10) + O(n)
＝ O(n) (因為n/5 + 7n/10 < n)
T(n) ＝ T(n-a)+T(a)+cn
＝ O(n^2)
(n)
/ \
(n-a) (a)
/ \
(n-2a) (a)
/ \
(n-3a) (a)
/ \
... (a)
/ \
(n-xa) (a) ,其中xa=n,且a=1時,此樹高最高
=> x= O(n) 為此樹樹高
而每層cost必小於O(n)
=> total cost = O(n^2)
有錯麻煩更正一下囉:-)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.235.131