作者sssmallwing (奄是涼小赫$__$)
看板Grad-ProbAsk
標題[理工] [資結]-時間複雜度
時間Thu Nov 12 15:30:48 2009
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
麻煩板上各位前輩!
感謝大家!!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.210.26
1F：推 FRAXIS:應該都是O(n)吧 11/12 17:07
2F：→ sssmallwing:可以提供一下想法嗎.....不知怎麼動手! 11/12 19:47
3F：推 uminchu185:1用替換法, 猜T(n)≦cn-b, c,b>0, 代回原式T(n)≦(cn/5 11/12 19:49
4F：→ uminchu185:-b)+c(7n/10+6)-b+dn= ...= (9/10c+d)+6c-2b≦ cn-b,取 11/12 19:51
5F：→ uminchu185:d≦c/10, c≦b/6, 因此T(n)= O(n). 11/12 19:52
6F：→ uminchu185:2用直接代入, 原式=T(n-2a)+T(a)+c(n-a)+T(0)+T(a)+ca, 11/12 19:55
7F：→ uminchu185:忽略T(0), => T(n-2a)+2T(a)+cn = T(n-3a)+3T(a)+2cn = 11/12 19:56
8F：→ uminchu185:...=T(n-ia)+iT(a)+(i-1)cn, 取i=n/a, =>T(0)+n/aT(a)+ 11/12 19:58
9F：→ uminchu185:(n/a-1)cn = O(n^2) 11/12 19:58
10F：→ uminchu185:供你參考, 有錯請多指教~ 11/12 20:00
11F：→ sssmallwing:謝U大 11/12 20:11