合并算法時(shí)間復(fù)雜度計(jì)算

合并排序的時(shí)間復(fù)雜度計(jì)算通信1304班：魯信金、易浩宇、劉子雄01020304目錄CONTENT合并排序時(shí)間復(fù)雜度如何學(xué)習(xí)方法及計(jì)算合并排序第三章標(biāo)題第二章標(biāo)題第四章標(biāo)題合并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（DivideandConquer）的一個(gè)非常典型的應(yīng)用。合并排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并。合并排序也叫歸并排序。第三章標(biāo)題第四章標(biāo)題時(shí)間復(fù)雜度第一章標(biāo)題計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定量描述了該算法的運(yùn)行時(shí)間。這是一個(gè)關(guān)于代表算法輸入值的字符串的長(zhǎng)度的函數(shù)。時(shí)間復(fù)雜度常用大O符號(hào)表述，不包括這個(gè)函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)。使用這種方式時(shí)，時(shí)間復(fù)雜度可被稱為是漸近的，它考察當(dāng)輸入值大小趨近無(wú)窮時(shí)的情況。第四章標(biāo)題第一章標(biāo)題方法及計(jì)算第二章標(biāo)題用T(n)表示輸入大小為n的數(shù)組時(shí)合并排序最壞的運(yùn)行時(shí)間。假設(shè)n是偶數(shù)。排序需要O(n)時(shí)間把輸入分成兩個(gè)大小為n/2的子數(shù)組，然后對(duì)每個(gè)子數(shù)組排序需要T(n/2)。最后需要O(n)把結(jié)果合并起來(lái)。所以我們得到這個(gè)關(guān)系式：T(n)<=2T(n/2)+O(n),或T(n)<=2T(n/2)+cn（當(dāng)n>2時(shí)，T(2)<=c）從這個(gè)關(guān)系式中并不能明顯看出T(n)是什么類型的函數(shù)，所以我們需要想辦法解出這個(gè)關(guān)系式，也就是遞歸求解。第四章標(biāo)題第一章標(biāo)題方法及計(jì)算第二章標(biāo)題方法求解有兩種基本的方法：1、最自然的方法是展開(kāi)關(guān)系式，通過(guò)分析最初幾級(jí)的運(yùn)行時(shí)間來(lái)得到一個(gè)通式，或者說(shuō)是規(guī)律，然后把每一級(jí)的運(yùn)行時(shí)間相加，即求得總的運(yùn)行時(shí)間。2、第二種方法是先猜出一個(gè)覺(jué)得合理的解，然后代入原來(lái)的關(guān)系式中驗(yàn)證。第四章標(biāo)題第一章標(biāo)題方法及計(jì)算第二章標(biāo)題展開(kāi)遞歸式基本的步驟：1、分析最初的幾級(jí)：在第0級(jí)時(shí)，我們只有一個(gè)大小為n的數(shù)組，這里需要最多cn時(shí)間。在第1級(jí)，我們有兩個(gè)子數(shù)組，每個(gè)大小為n/2，分別需cn/2時(shí)間，所以總的時(shí)間是2*(cn/2)=cn。在第2級(jí)，我們有四個(gè)子數(shù)組，每個(gè)大小為n/4，分別需要cn/4時(shí)間，所以總的時(shí)間還是4*(cn/4)=cn。2、得出規(guī)律：可以看到在第j級(jí)時(shí)，我們有2j個(gè)子數(shù)組，每個(gè)大小為cn/2j，分別需要cn/2j時(shí)間，所以這級(jí)總的運(yùn)行時(shí)間為2j(cn/2j)=cn.3、求和：我們已經(jīng)求得每一級(jí)需要的運(yùn)行時(shí)間。對(duì)于一個(gè)大小為n的數(shù)組，遞歸最多有l(wèi)ogn層，所以總的運(yùn)行時(shí)間為O(nlogn)。第四章標(biāo)題第一章標(biāo)題方法及計(jì)算第二章標(biāo)題更通用的遞歸式：上面的分析都是基于每個(gè)問(wèn)題被分成2個(gè)子問(wèn)題。如果現(xiàn)在我們把每個(gè)問(wèn)題分成q個(gè)大小為n/2的子問(wèn)題，我們得到一個(gè)更通用的遞歸式T(n)<=qT(n/2)+cn當(dāng)n>2時(shí)，T(2)<=c

當(dāng)q=2時(shí)就是我們上面分析的情況。接下來(lái)我們分析q>2和q=1的情況。第四章標(biāo)題第一章標(biāo)題方法及計(jì)算第二章標(biāo)題q>2的情況：還是采用基本的步驟展開(kāi)：?分析：這里我們假設(shè)q=3。在第0級(jí)時(shí)，只有一個(gè)大小為n的問(wèn)題，需要cn時(shí)間。在第1級(jí)，我們有q個(gè)子問(wèn)題，每個(gè)大小n/2，需要cn/2時(shí)間，所以總的時(shí)間為(q/2)cn。在第2級(jí)，有q2個(gè)字問(wèn)題，每個(gè)大小n/4，需要cn/4時(shí)間，總的時(shí)間為(q2/4)cn。?得出規(guī)律：在任意一級(jí)j，有qj個(gè)字問(wèn)題，每個(gè)大小為n/2j，所以總的時(shí)間為qj(cn/2j)=(q/2)jcn。求和：對(duì)于大小為n的問(wèn)題，總的層數(shù)還是不變，所以第四章標(biāo)題第一章標(biāo)題第二章標(biāo)題令r=q/2，則上式變成了方法及計(jì)算這里用到了幾何級(jí)數(shù)的一個(gè)公式。如果我們有等式兩邊同時(shí)乘以r得到兩式相減得到第四章標(biāo)題第一章標(biāo)題第二章標(biāo)題所以方法及計(jì)算回到T(n)上來(lái)。因?yàn)閞=q/2是常數(shù)，所以現(xiàn)在問(wèn)題變成了求

。這里用上對(duì)數(shù)的換底公式，當(dāng)a>1,b>1時(shí)。

所以最終得到從結(jié)果看得出，運(yùn)行時(shí)間是大于線性的因?yàn)?/p>

。q=4時(shí)運(yùn)行時(shí)間是O(n2)。第四章標(biāo)題第一章標(biāo)題方法及計(jì)算第二章標(biāo)題q=1的情況:?分析：第0級(jí)時(shí)，只有一個(gè)大小為n的問(wèn)題，需要cn時(shí)間。第1級(jí)時(shí)，問(wèn)題大小為n/2，需要cn/2時(shí)間。第2級(jí)時(shí)，問(wèn)題大小為n/4，需要cn/4時(shí)間。?規(guī)律：我們看到在任意級(jí)j都只有一個(gè)問(wèn)題，大小為n/2j，需要cn/2j時(shí)間來(lái)完成。?求和：總的層數(shù)還是logn。還是用幾何級(jí)數(shù)可以得出它最終收斂于2。所以第四章標(biāo)題第一章標(biāo)題方法及計(jì)算第二章標(biāo)題

通過(guò)對(duì)上面三種情況，q=1,q=2,q>2的分析我們得出三種不同的運(yùn)行時(shí)間。q=1時(shí)，運(yùn)行時(shí)間是線性的。q=2時(shí)是O(nlogn)。q>2時(shí)是多項(xiàng)式級(jí)數(shù)。造成這種差別的原因主要在于在遞歸時(shí)大部分的工作完成的階段。q=1時(shí)，第0級(jí)就已經(jīng)完成了一半的工作，而當(dāng)q>2時(shí)，大部分工作卻是在遞歸底層完成。所以q=2可以說(shuō)是介于兩者之間的分水嶺–每一層完成工作的總量是相同的，給了我們較優(yōu)的O(n