在歸并排序或者和二叉樹相關(guān)的算法中望几，我們需要將處理的數(shù)據(jù)，分割成兩部分萤厅，然后再組合橄抹，此時關(guān)于時間復(fù)雜度，就成為了這樣
T(N) = 2T(N/2) + O(N)
我們知道惕味，歸并排序的時間復(fù)雜度是 O(NlogN)楼誓，那么這是怎么推導(dǎo)出來的呢？或者說更抽象一點名挥，類似于這種分治手段的時間復(fù)雜度怎么計算呢疟羹？在《算法導(dǎo)論》中提出了主方法的概念，如下
image
正如圖中所示禀倔，由于a,b的不同關(guān)系榄融，T(n)有三種可能性，接下來就來詳細(xì)推導(dǎo)這個過程救湖。
首先我們先得做一個假定剃袍，T(1)=1,因為如果數(shù)據(jù)只有一個的話，我們根本不需要排序捎谨，只需要遍歷一下即可民效，然后設(shè) N = b的k次方憔维，這樣就去掉了n這個變量，同時a畏邢，b,n,d就被連接起來业扒，我們只需要對式子進(jìn)行化簡，并注意合并舒萎，即可完成推導(dǎo)……
詳細(xì)推導(dǎo)可以查看視頻哦
<mpvideosnap class="js_uneditable custom_select_card channels_iframe custom_select_card_selected" data-pluginname="videosnap" data-id="export/UzFfAgtgekIEAQAAAAAA--gSadFMCwAAAAstQy6ubaLX4KHWvLEZgBPEmKFMZDxFMZb4zNPgMIuB0ingUHP1-wpoz7cvChdu" data-url="https://findermp.video.qq.com/251/20350/stodownload?encfilekey=wMyh8PvoRic4QvEiapufQCa94hDqSSU4IKW8K58jG1YvDXDoptXAJXtZyueoBehakGnJkjCyzmJKpjTpEg8oyofI2dbmsdS51Lkb4r8LTMnHExdeGSdbXkluWia963aSbWhJJibWVA9OEYoUSfXwdqNnKynFuX7IlRADoU6gQlq5tuy1iceicjD3Whhw&adaptivelytrans=0&bizid=1023&dotrans=0&hy=SZ&idx=1&m=61f89de81cc63761443191c481fc10dc&token=x5Y29zUxcibB5swgCmOQ85rZu3a3nmtpKFuV6NLpBe6wgTictLQuhoaA4EBN2SzOAG" data-headimgurl="http://wx.qlogo.cn/finderhead/lXKSjDuiaN7xwWmRxpzbTFUXr3xW2Qia5U66m39pNpUNA/0" data-username="v2_060000231003b20faec8cae0891cc4d6cf06ee31b077c6493cb053a5e0f8c8659f89829db088@finder" data-nickname="小松漫步" data-desc="遞歸時間復(fù)雜度計算大殺器" data-nonceid="2106970874272682350" data-type="video" contenteditable="false" style="margin: 0px 1px; padding: 0px; max-width: 100%; overflow-wrap: break-word !important; box-sizing: border-box !important; position: relative; display: inline-block; width: 575.109px;">image
小松漫步遞歸時間復(fù)雜度計算大殺器視頻號</mpvideosnap>推導(dǎo)所用到的知識基本大學(xué)都學(xué)過程储，但是小松在自己推導(dǎo)的時候，總是卡殼臂寝，學(xué)習(xí)只要 20 分鐘章鲤，但是錄視頻卻錄了 1 個小時，剪輯更是花了 2 小時……不過咆贬，這也讓小松對于推導(dǎo)過程爛熟于心败徊，加油吧，打工人公眾號回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】掏缎，即可獲取pdf版
