[理工] 資結時間複雜度 easion0317 PTT批踢踢實業坊

作者: easion0317 (仲夏螢火蟲) 2015-06-24 21:52:38

http://i.imgur.com/iHZ6v3V.jpg
題目在圖上求big oh
遞回怎麼去假設出式子再求時間複雜度

作者: goldflower (金色小黃花) 2015-06-24 23:22:00

你從n往下展應該會比較清楚

作者: harryron9 (兩個世界) 2015-06-25 09:30:00

某方面來講你已經寫完了T(n)=2*T(n/2)+2*T(n/2)=4T(n/2)=16T(n/4)...

作者: easion0317 (仲夏螢火蟲) 2015-06-25 21:20:00

http://i.imgur.com/bE9XmtR.jpg看不是很懂詳解的式子我的式子列的跟h大一樣

作者: goldflower (金色小黃花) 2015-06-25 22:47:00

喔喔他是用master method做的直接代入就好n^log2(2)=n > 常數所以T(n)=theta(n)

作者: easion0317 (仲夏螢火蟲) 2015-06-26 11:41:00

這題我是分析一個母問題切割成兩個子問題可是MM的公式T(n)=aT(n/b)+f(n)這種形式才可使用這題怎麼用MM去看

作者: goldflower (金色小黃花) 2015-06-26 21:30:00

因為他寫recursive部分的theta(1)那邊那個是指乘法和加法的部分這個是是為常數而且是每層遞增所以符合f(n)的條件

繼續閱讀