[問題] 97中山資結

看板Grad-ProbAsk作者 (depend)時間15年前 (2009/03/24 16:50), 編輯推噓0(0推 0噓 4→)
留言4則, 3人參與, 最新討論串1/2 (看更多)
中山資結的第一題 T(n)= 1 if n=1 4T(n/2)+theta(n^2) if n>1 設T(n)=O(n^2) =>T(n)=4O(n^2/2^2)+n^2=O(n^2) 這個步驟是哪裡出錯呢??? 那正確的複雜度應該要怎麼算阿 我用數學的方法計算可是怎麼算都不是n^2*(logn)耶...?? 麻煩高手解答 謝謝>"< -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.116.142.19
→
03/24 17:15, , 1F
master theorem; n^(log2 4)=n^2=θ(n^2)
03/24 17:15, 1F
→
03/24 17:16, , 2F
∴T(n)=θ( (n^2)*logn )
03/24 17:16, 2F
→
03/24 17:21, , 3F
可是他的題目有說不能用公式解耶>"<
03/24 17:21, 3F
→
03/24 17:56, , 4F
令n=2^k 代進去解 並不會很難解
03/24 17:56, 4F
‣ 更多 depend 的文章
文章代碼(AID): #19o9xP4g (Grad-ProbAsk)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共2篇)
‣ 更多 depend 的文章
文章代碼(AID): #19o9xP4g (Grad-ProbAsk)