[理工] [資結]-時間複雜度

[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

麻煩板上各位前輩!
感謝大家!!

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.113.210.26
推 FRAXIS:應該都是O(n)吧
→ sssmallwing:可以提供一下想法嗎.....不知怎麼動手!
推 uminchu185:1用替換法, 猜T(n)≦cn-b, c,b>0, 代回原式T(n)≦(cn/5
→ uminchu185:-b)+c(7n/10+6)-b+dn= ...= (9/10c+d)+6c-2b≦ cn-b,取
→ uminchu185:d≦c/10, c≦b/6, 因此T(n)= O(n).
→ uminchu185:2用直接代入, 原式=T(n-2a)+T(a)+c(n-a)+T(0)+T(a)+ca,
→ uminchu185:忽略T(0), => T(n-2a)+2T(a)+cn = T(n-3a)+3T(a)+2cn =
→ uminchu185:...=T(n-ia)+iT(a)+(i-1)cn, 取i=n/a, =>T(0)+n/aT(a)+
→ uminchu185:(n/a-1)cn = O(n^2)
→ uminchu185:供你參考, 有錯請多指教~
→ sssmallwing:謝U大