Re: [理工] [資結]-時間複雜度
※ 引述《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
推
11/13 22:34, , 1F
11/13 22:34, 1F
→
11/13 22:36, , 2F
11/13 22:36, 2F
→
11/13 22:43, , 3F
11/13 22:43, 3F
→
11/15 00:30, , 4F
11/15 00:30, 4F
討論串 (同標題文章)