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

看板Grad-ProbAsk作者 (奄是涼小赫$__$)時間16年前 (2009/11/12 15:30), 編輯推噓2(2推 0噓 9→)
留言11則, 3人參與, 最新討論串12/38 (看更多)
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
推
11/12 17:07, , 1F
應該都是O(n)吧
11/12 17:07, 1F
→
11/12 19:47, , 2F
可以提供一下想法嗎.....不知怎麼動手!
11/12 19:47, 2F
推
11/12 19:49, , 3F
1用替換法, 猜T(n)≦cn-b, c,b>0, 代回原式T(n)≦(cn/5
11/12 19:49, 3F
→
11/12 19:51, , 4F
-b)+c(7n/10+6)-b+dn= ...= (9/10c+d)+6c-2b≦ cn-b,取
11/12 19:51, 4F
→
11/12 19:52, , 5F
d≦c/10, c≦b/6, 因此T(n)= O(n).
11/12 19:52, 5F
→
11/12 19:55, , 6F
2用直接代入, 原式=T(n-2a)+T(a)+c(n-a)+T(0)+T(a)+ca,
11/12 19:55, 6F
→
11/12 19:56, , 7F
忽略T(0), => T(n-2a)+2T(a)+cn = T(n-3a)+3T(a)+2cn =
11/12 19:56, 7F
→
11/12 19:58, , 8F
...=T(n-ia)+iT(a)+(i-1)cn, 取i=n/a, =>T(0)+n/aT(a)+
11/12 19:58, 8F
→
11/12 19:58, , 9F
(n/a-1)cn = O(n^2)
11/12 19:58, 9F
→
11/12 20:00, , 10F
供你參考, 有錯請多指教~
11/12 20:00, 10F
→
11/12 20:11, , 11F
謝U大
11/12 20:11, 11F
‣ 更多 sssmallwing 的文章
文章代碼(AID): #1A-xcgKG (Grad-ProbAsk)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 12 之 38 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共38篇)
‣ 更多 sssmallwing 的文章
文章代碼(AID): #1A-xcgKG (Grad-ProbAsk)