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

1、合并排序的時(shí)間復(fù)雜度計(jì)算通信1304班：魯信金、易浩宇、劉子雄01020304目錄 CONTENT合并排序時(shí)間復(fù)雜度如何學(xué)習(xí)方法及計(jì)算合并排序第三章標(biāo)題第二章標(biāo)題第四章標(biāo)題合并排序是建立在歸并操作上的一種有效的排合并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（序算法。該算法是采用分治法（Divide and Divide and ConquerConquer）的一個(gè)非常典型的應(yīng)用。合并排序法）的一個(gè)非常典型的應(yīng)用。合并排序法是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新是將兩個(gè)（或兩個(gè)以上）有序表合并成一個(gè)新的有序表，即把待排序序列分為若干個(gè)子序列，的有序表，即把待排序序列分為若

2、干個(gè)子序列，每個(gè)子序列是有序的。然后再把有序子序列合每個(gè)子序列是有序的。然后再把有序子序列合并為整體有序序列。將已有序的子序列合并，并為整體有序序列。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為一個(gè)有序表，稱為2-2-路歸并。合并排序也叫歸路歸并。合并排序也叫歸并排序。并排序。第三章標(biāo)題第四章標(biāo)題時(shí)間復(fù)雜度第一章標(biāo)題計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定量描述了該算法的運(yùn)行時(shí)間。這是一個(gè)關(guān)于代表算法輸入值的字符串的長度的函數(shù)。時(shí)間

3、復(fù)雜度常用大O符號(hào)表述，不包括這個(gè)函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)。使用這種方式時(shí)，時(shí)間復(fù)雜度可被稱為是漸近的，它考察當(dāng)輸入值大小趨近無窮時(shí)的情況。第四章標(biāo)題第一章標(biāo)題方法及計(jì)算第二章標(biāo)題用用 T(n) T(n) 表示輸入大小為表示輸入大小為 n n 的數(shù)組時(shí)合并排序最壞的數(shù)組時(shí)合并排序最壞的運(yùn)行時(shí)間。假設(shè)的運(yùn)行時(shí)間。假設(shè) n n 是偶數(shù)。排序需要是偶數(shù)。排序需要 O(n) O(n) 時(shí)間時(shí)間把輸入分成兩個(gè)大小為把輸入分成兩個(gè)大小為 n/2 n/2 的子數(shù)組，然后對(duì)每個(gè)的子數(shù)組，然后對(duì)每個(gè)子數(shù)組排序需要子數(shù)組排序需要 T(n/2) T(n/2)。最后需要。最后需要 O(n) O(n) 把結(jié)果合把結(jié)果合并

4、起來。所以我們得到這個(gè)關(guān)系式：并起來。所以我們得到這個(gè)關(guān)系式：T(n) = 2T(n/2) + O(n), 或 T(n) 2時(shí)，T(2) = c）從這個(gè)關(guān)系式中并不能明顯看出從這個(gè)關(guān)系式中并不能明顯看出 T(n) T(n) 是什么類型的函數(shù)，是什么類型的函數(shù)，所以我們需要想辦法解出這個(gè)關(guān)系式，也就是遞歸求解所以我們需要想辦法解出這個(gè)關(guān)系式，也就是遞歸求解。第四章標(biāo)題第一章標(biāo)題方法及計(jì)算第二章標(biāo)題方法求方法求解解有兩種基本的方法：有兩種基本的方法：1 1、最自然的方法是展開關(guān)系式，通過分最自然的方法是展開關(guān)系式，通過分析最初幾級(jí)的運(yùn)行時(shí)間來得到一個(gè)通式，析最初幾級(jí)的運(yùn)行時(shí)間來得到一個(gè)通式，或者說

5、是規(guī)律，然后把每一級(jí)的運(yùn)行時(shí)或者說是規(guī)律，然后把每一級(jí)的運(yùn)行時(shí)間相加，即求得總的運(yùn)行時(shí)間。間相加，即求得總的運(yùn)行時(shí)間。2 2、第二種方法是先猜出一個(gè)覺得合理的第二種方法是先猜出一個(gè)覺得合理的解，然后代入原來的關(guān)系式中驗(yàn)證。解，然后代入原來的關(guān)系式中驗(yàn)證。第四章標(biāo)題第一章標(biāo)題方法及計(jì)算方法及計(jì)算第二章標(biāo)題展開遞歸式基本的步驟：1 1、分析最初的幾級(jí)：在第分析最初的幾級(jí)：在第0 0級(jí)時(shí)，我們只有一個(gè)大級(jí)時(shí)，我們只有一個(gè)大小為小為 n n 的數(shù)組，這里需要最多的數(shù)組，這里需要最多 cn cn 時(shí)間。在第時(shí)間。在第1 1級(jí)，級(jí)，我們有兩個(gè)子數(shù)組，每個(gè)大小為我們有兩個(gè)子數(shù)組，每個(gè)大小為 n/2 n/2，

6、分別需，分別需cn/2 cn/2 時(shí)間，所以總的時(shí)間是時(shí)間，所以總的時(shí)間是 2 2* *(cn/2) = cn(cn/2) = cn。在第。在第2 2級(jí)，級(jí)，我們有四個(gè)子數(shù)組，每個(gè)大小為我們有四個(gè)子數(shù)組，每個(gè)大小為 n/4 n/4，分別需要，分別需要 cn/4 cn/4 時(shí)間，所以總的時(shí)間還是時(shí)間，所以總的時(shí)間還是 4 4* *(cn/4) = cn(cn/4) = cn。2 2、得出規(guī)律：可以看到在第得出規(guī)律：可以看到在第 j j 級(jí)時(shí)，我們有級(jí)時(shí)，我們有2j2j個(gè)個(gè)子數(shù)組，每個(gè)大小為子數(shù)組，每個(gè)大小為 cn/2j cn/2j，分別需要，分別需要cn/2jcn/2j時(shí)間，時(shí)間，所以這級(jí)總的運(yùn)

7、行時(shí)間為所以這級(jí)總的運(yùn)行時(shí)間為2j(cn/2j) = cn.2j(cn/2j) = cn.3 3、求和：我們已經(jīng)求得每一級(jí)需要的運(yùn)行時(shí)間。對(duì)求和：我們已經(jīng)求得每一級(jí)需要的運(yùn)行時(shí)間。對(duì)于一個(gè)大小為于一個(gè)大小為 n n 的數(shù)組，遞歸最多有的數(shù)組，遞歸最多有l(wèi)ognlogn層，所以層，所以總的運(yùn)行時(shí)間為總的運(yùn)行時(shí)間為 O(nlogn) O(nlogn)。第四章標(biāo)題第一章標(biāo)題方法及計(jì)算第二章標(biāo)題更通用的遞歸式更通用的遞歸式：上面的分析都是基于每個(gè)問題被分成2個(gè)子問題。如果現(xiàn)在我們把每個(gè)問題分成 q 個(gè)大小為 n/2 的子問題，我們得到一個(gè)更通用的遞歸式T(n) 2時(shí)，T(2) 2 和 q=1的情況。第

8、四章標(biāo)題第一章標(biāo)題方法及計(jì)算方法及計(jì)算第二章標(biāo)題q2q2的情況的情況：還是采用基本的步驟展開：還是采用基本的步驟展開：分析：這里我們假設(shè)分析：這里我們假設(shè) q=3 q=3。在第。在第0 0級(jí)時(shí)，只有一個(gè)級(jí)時(shí)，只有一個(gè)大小為大小為n n的問題，需要的問題，需要cncn時(shí)間。在第時(shí)間。在第1 1級(jí)，我們有級(jí)，我們有q q個(gè)個(gè)子問題，每個(gè)大小子問題，每個(gè)大小n/2n/2，需要，需要cn/2cn/2時(shí)間，所以總的時(shí)時(shí)間，所以總的時(shí)間為間為(q/2)cn(q/2)cn。在第。在第2 2級(jí)，有級(jí)，有q2q2個(gè)字問題，每個(gè)大小個(gè)字問題，每個(gè)大小n/4n/4，需要，需要cn/4cn/4時(shí)間，總的時(shí)間為時(shí)間，總

9、的時(shí)間為(q2/4)cn(q2/4)cn。得出規(guī)律：在任意一級(jí)得出規(guī)律：在任意一級(jí)j j，有，有qjqj個(gè)字問題，每個(gè)大個(gè)字問題，每個(gè)大小為小為n/2jn/2j，所以總的時(shí)間為，所以總的時(shí)間為qj(cn/2j) = (q/2)jcnqj(cn/2j) = (q/2)jcn。求和：對(duì)于大小為求和：對(duì)于大小為n n的問題，總的層數(shù)還是不變，所的問題，總的層數(shù)還是不變，所以以第四章標(biāo)題第一章標(biāo)題第二章標(biāo)題令令 r = q/2r = q/2，則上式變成了，則上式變成了方法及計(jì)算這里用到了幾何級(jí)數(shù)的一個(gè)公式。如果我們這里用到了幾何級(jí)數(shù)的一個(gè)公式。如果我們有有等式兩邊同時(shí)乘以等式兩邊同時(shí)乘以r r得到得到

10、兩式相減得到兩式相減得到第四章標(biāo)題第一章標(biāo)題第二章標(biāo)題所以所以方法及計(jì)算回到回到T(n)T(n)上來。因?yàn)樯蟻怼Ｒ驗(yàn)閞=q/2r=q/2是常數(shù)，所以是常數(shù)，所以現(xiàn)在問題變成了求現(xiàn)在問題變成了求 。這里用上對(duì)數(shù)的換底公式，。這里用上對(duì)數(shù)的換底公式，當(dāng)當(dāng)a1, b1a1, b1時(shí)時(shí) 。 所以所以最終得到最終得到從結(jié)果看得出，運(yùn)行時(shí)間是大于線性的因?yàn)?。q=4時(shí)運(yùn)行時(shí)間是O(n2)。第四章標(biāo)題第一章標(biāo)題方法及計(jì)算第二章標(biāo)題q=1的情況:分析：第分析：第0 0級(jí)時(shí)，只有一個(gè)大小為級(jí)時(shí)，只有一個(gè)大小為n n的問題，需要的問題，需要cncn時(shí)時(shí)間。第間。第1 1級(jí)時(shí)，問題大小為級(jí)時(shí)，問題大小為n/2n/2

11、，需要，需要cn/2cn/2時(shí)間。第時(shí)間。第2 2級(jí)級(jí)時(shí)，問題大小為時(shí)，問題大小為n/4n/4，需要，需要cn/4cn/4時(shí)間。時(shí)間。規(guī)律：我們看到在任意級(jí)規(guī)律：我們看到在任意級(jí)j j都只有一個(gè)問題，大小為都只有一個(gè)問題，大小為n/2jn/2j，需要，需要cn/2jcn/2j時(shí)間來完成。時(shí)間來完成。求和：總的層數(shù)還是求和：總的層數(shù)還是lognlogn。還是用幾何級(jí)數(shù)可以得出它最終收斂于還是用幾何級(jí)數(shù)可以得出它最終收斂于2 2。所以。所以第四章標(biāo)題第一章標(biāo)題方法及計(jì)算第二章標(biāo)題 通過對(duì)上面三種情況，通過對(duì)上面三種情況，q = 1, q = 2, q = 1, q = 2, q 2q 2的分析我們

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