作者cormen5566 (怕热非洲土着)
看板Grad-ProbAsk
标题Re: [理工] [资结]-时间复杂度
时间Fri Nov 13 16:30:19 2009
※ 引述《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
1F：推 yesa315:我觉得是O(n) n/5+7n/10 = 9n/10 < n 11/13 22:34
2F：→ yesa315:这种树状的递回 最多只有到O(n log n ) 当每层cost为 n 时 11/13 22:36
3F：→ yesa315:对吧!? 11/13 22:43
4F：→ cormen5566:当a=1时，树高不就是n了吗? 11/15 00:30