遞歸方程求解--主定理

重點(diǎn)提示

  • 遞歸樹分析法
  • 適用情形與不適用情形

具有遞歸結(jié)構(gòu)的算法的運(yùn)行時(shí)間分析

主定理

假設(shè)某個(gè)具有遞歸結(jié)構(gòu)的算法的運(yùn)行時(shí)間用T(n)=aT(n/b)+f(n)表示，其中f(n)表示將原問題分解成子問題的時(shí)間跟將子問題的解合并的時(shí)間的總和，

  • 如果f(n)多項(xiàng)式小于n^{\log_ba}，則T(n)的上限就是n^{\log_ba}；
  • 如果f(n)多項(xiàng)式大于n^{\log_ba}，且 af(n/b)\leq cf(n)，其中c<1，則T(n)的上限就是的上限就是f(n)；
  • 如果f(n)跟n^{\log_ba}有相同的增長階，則T(n)的上線就是n^{\log_ba}\log n；

遞歸樹角度理解主定理

主定理證明--遞歸樹.png
  • 整個(gè)樹的開銷被葉子節(jié)點(diǎn)的總開銷控制；
  • 整個(gè)樹的開銷被根節(jié)點(diǎn)的開銷控制；
  • 整個(gè)樹的開銷被均勻分?jǐn)偟綐涞母鱾€(gè)層級(jí)了；

注：

f(n)跟n^{\log_ba}之間存在5種關(guān)系

  • f(n)非多項(xiàng)式小于n^{\log_ba}（主定理不適用）；
  • f(n)多項(xiàng)式小于n^{\log_ba}（主定理適用）；
  • f(n)跟n^{\log_ba}增長階相同（主定理適用）；
  • f(n)多項(xiàng)式大于n^{\log_ba}（主定理適用）；
  • f(n)非多項(xiàng)式大于n^{\log_ba}（主定理不適用）；
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 閱讀經(jīng)典——《算法導(dǎo)論》04 在算法分析中，我們通常會(huì)得到一個(gè)關(guān)于輸入規(guī)模n的遞歸式，形式如下： （式4-1） T...
    金戈大王閱讀 16,640評(píng)論 6贊 5
  • 每一個(gè)想你的日子，都是傷口。 我不知道，我并不遼闊的肌膚上，能安置多少次不會(huì)愈合的痛。或許終將有天會(huì)破潰腐爛而亡。...
    傾蓶閱讀 477評(píng)論 0贊 5
  • 吃得苦中苦方為人上人！ 晚安！
    Smile_Zhangjie閱讀 238評(píng)論 1贊 2
  • 為了將使用PyTorch訓(xùn)練的深度學(xué)習(xí)模型，集成進(jìn)C++桌面端應(yīng)用中，選擇采用ONNX將模型轉(zhuǎn)化為其他有C++接口...
    藥柴閱讀 7,782評(píng)論 0贊 0

友情鏈接更多精彩內(nèi)容