[理工] 資結 時間複雜度
作者: easion0317 (仲夏螢火蟲) 2015-06-24 21:52:38
題目在圖上 求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
" target="_blank" rel="nofollow">看不是很懂詳解的式子我的式子列的跟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)的條件