[理工] 資結 時間複雜度

看板Grad-ProbAsk作者 (仲夏螢火蟲)時間10年前 (2015/06/24 21:52), 編輯推噓4(4推 0噓 10→)
留言14則, 3人參與, 最新討論串3/12 (看更多)
http://i.imgur.com/iHZ6v3V.jpg
題目在圖上 求big oh 遞回怎麼去假設出式子 再求時間複雜度 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.138.157.167 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1435153960.A.99E.html
推
06/24 23:22, , 1F
你從n往下展應該會比較清楚
06/24 23:22, 1F
推
06/25 09:30, , 2F
某方面來講你已經寫完了
06/25 09:30, 2F
推
06/25 09:34, , 3F
T(n)=2*T(n/2)+2*T(n/2)=4T(n/2)=16T(n/4)...
06/25 09:34, 3F
→
06/25 21:20, , 4F
06/25 21:20, 4F
→
06/25 21:20, , 5F
看不是很懂詳解的式子
06/25 21:20, 5F
→
06/25 21:21, , 6F
我的式子列的跟h大一樣
06/25 21:21, 6F
→
06/25 22:47, , 7F
喔喔 他是用master method做的 直接代入就好
06/25 22:47, 7F
→
06/25 22:48, , 8F
n^log2(2)=n > 常數 所以T(n)=theta(n)
06/25 22:48, 8F
→
06/26 11:41, , 9F
這題我是分析 一個母問題切割成兩個子問題 可是MM的
06/26 11:41, 9F
→
06/26 11:41, , 10F
公式T(n)=aT(n/b)+f(n)這種形式才可使用
06/26 11:41, 10F
→
06/26 11:42, , 11F
這題怎麼用MM去看
06/26 11:42, 11F
推
06/26 21:30, , 12F
因為他寫recursive部分的theta(1)那邊 那個是指乘法
06/26 21:30, 12F
→
06/26 21:30, , 13F
和加法的部分 這個是是為常數 而且是每層遞增
06/26 21:30, 13F
→
06/26 21:30, , 14F
所以符合f(n)的條件
06/26 21:30, 14F
‣ 更多 easion0317 的文章
文章代碼(AID): #1LYhOecU (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 3 之 12 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共12篇)
‣ 更多 easion0317 的文章
文章代碼(AID): #1LYhOecU (Grad-ProbAsk)