究竟為什么，快速排序的時(shí)間復(fù)雜度是n*lg(n)？ | 經(jīng)典面試題
最煩面試官問(wèn)，“為什么XX算法的時(shí)間復(fù)雜度是OO”，今后，不再懼怕這類問(wèn)題。
快速排序分為這么幾步：
第一步，先做一次partition；
partition使用第一個(gè)元素t=arr[low]為哨兵，把數(shù)組分成了兩個(gè)半?yún)^(qū)：
左半?yún)^(qū)比t大
右半?yún)^(qū)比t小
第二步，左半?yún)^(qū)遞歸；
第三步，右半?yún)^(qū)遞歸；
偽代碼為：
void quick_sort(int[]arr, int low, int high){
???????? if(low== high) return;
???????? int i = partition(arr, low, high);
???????? quick_sort(arr, low, i-1);
???????? quick_sort(arr, i+1, high);
}
為啥，快速排序，時(shí)間復(fù)雜度是O(n*lg(n))呢？
今天和大家聊聊時(shí)間復(fù)雜度。
畫外音：往下看，第三類方法很牛逼。
第一大類，簡(jiǎn)單規(guī)則
為方便記憶，先總結(jié)幾條簡(jiǎn)單規(guī)則，熱熱身。
規(guī)則一：“有限次操作”的時(shí)間復(fù)雜度往往是O(1)。
例子：交換兩個(gè)數(shù)a和b的值。
void swap(int& a, int& b){
???????? int t=a;
???????? a=b;
???????? b=t;
}
分析：通過(guò)了一個(gè)中間變量t，進(jìn)行了3次操作，交換了a和b的值，swap的時(shí)間復(fù)雜度是O(1)。
畫外音：這里的有限次操作，是指不隨數(shù)據(jù)量的增加，操作次數(shù)增加。
規(guī)則二：“for循環(huán)”的時(shí)間復(fù)雜度往往是O(n)。
例子：n個(gè)數(shù)中找到最大值。
int max(int[] arr, int n){
???????? int temp = -MAX;
???????? for(int i=0;i
?????????????????? if(arr[i]>temp) temp=arr[i];
???????? return temp;
}
分析：通過(guò)一個(gè)for循環(huán)，將數(shù)據(jù)集遍歷，每次遍歷，都只執(zhí)行“有限次操作”，計(jì)算的總次數(shù)，和輸入數(shù)據(jù)量n呈線性關(guān)系。
規(guī)則三：“樹(shù)的高度”的時(shí)間復(fù)雜度往往是O(lg(n))。
分析：樹(shù)的總節(jié)點(diǎn)個(gè)數(shù)是n，則樹(shù)的高度是lg(n)。
在一棵包含n個(gè)元素二分查找樹(shù)上進(jìn)行二分查找，其時(shí)間復(fù)雜度是O(lg(n))。
對(duì)一個(gè)包含n個(gè)元素的堆頂元素彈出后，調(diào)整成一個(gè)新的堆，其時(shí)間復(fù)雜度也是O(lg(n))。
第二大類：組合規(guī)則
通過(guò)簡(jiǎn)單規(guī)則的時(shí)間復(fù)雜度，來(lái)求解組合規(guī)則的時(shí)間復(fù)雜度。
例如：n個(gè)數(shù)冒泡排序。
void bubble_sort(int[] arr, int n){
???for(int i=0;i
???????for(int j=0;j
???????????if(arr[j]>arr[j+1])
??????????????? swap(arr[j], arr[j+1]);
}
分析：冒泡排序，可以看成三個(gè)規(guī)則的組合：
1. 外層for循環(huán)
2. 內(nèi)層for循環(huán)
3. 最內(nèi)層的swap
故，冒泡排序的時(shí)間復(fù)雜度為：
O(n) * O(n) * O(1) = O(n^2)
又例如：TopK問(wèn)題，通過(guò)建立k元素的堆，來(lái)從n個(gè)數(shù)中求解最大的k個(gè)數(shù)。
先用前k個(gè)元素生成一個(gè)小頂堆，這個(gè)小頂堆用于存儲(chǔ)，當(dāng)前最大的k個(gè)元素。
接著，從第k+1個(gè)元素開(kāi)始掃描，和堆頂（堆中最小的元素）比較，如果被掃描的元素大于堆頂，則替換堆頂?shù)脑?，并調(diào)整堆，以保證堆內(nèi)的k個(gè)元素，總是當(dāng)前最大的k個(gè)元素。
直到，掃描完所有n-k個(gè)元素，最終堆中的k個(gè)元素，就是為所求的TopK。
偽代碼：
heap[k] = make_heap(arr[1, k]);
for(i=k+1 to n){
???????? adjust_heap(heep[k],arr[i]);
}
return heap[k];
分析：可以看成三個(gè)規(guī)則的組合：
1. 新建堆
2. for循環(huán)
3. 調(diào)整堆
故，用堆求解TopK，時(shí)間復(fù)雜度為：
O(k) + O(n) * O(lg(k)) = O(n*lg(k))
畫外音：注意哪些地方用加，哪些地方用乘；哪些地方是n，哪些地方是k。
第三大類，遞歸求解
簡(jiǎn)單規(guī)則和組合規(guī)則可以用來(lái)求解非遞歸的算法的時(shí)間復(fù)雜度。對(duì)于遞歸的算法，該怎么分析呢？
接下來(lái)，通過(guò)幾個(gè)案例，來(lái)說(shuō)明如何通分析遞歸式，來(lái)分析遞歸算法的時(shí)間復(fù)雜度。
案例一：計(jì)算 1到n的和，時(shí)間復(fù)雜度分析。
如果用非遞歸的算法：
int sum(int n){
???????? int result=0;
???????? for(int i=0;i
?????????????????? result += i;
???????? return result;
}
根據(jù)簡(jiǎn)單規(guī)則，for循環(huán)，sum的時(shí)間復(fù)雜度是O(n)。
但如果是遞歸算法，就沒(méi)有這么直觀了：
int sum(int n){
???????? if (n==1) return 1;
???????? return n+sum(n-1);
}
如何來(lái)進(jìn)行時(shí)間復(fù)雜度分析呢？
用f(n)來(lái)表示數(shù)據(jù)量為n時(shí)，算法的計(jì)算次數(shù)，很容易知道：
當(dāng)n=1時(shí)，sum函數(shù)只計(jì)算1次
畫外音：if (n==1) return 1;
即：
f(1)=1【式子A】
不難發(fā)現(xiàn)，當(dāng)n不等于1時(shí)：
f(n)的計(jì)算次數(shù)，等于f(n-1)的計(jì)算次數(shù)，再加1次計(jì)算
畫外音：return n+sum(n-1);
即：
f(n)=f(n-1)+1【式子B】
【式子B】不斷的展開(kāi)，再配合【式子A】：
畫外音：這一句話，是分析這個(gè)算法的關(guān)鍵。
f(n)=f(n-1)+1
f(n-1)=f(n-2)+1
…
f(2)=f(1)+1
f(1)=1
上面共n個(gè)等式，左側(cè)和右側(cè)分別相加：
f(n)+f(n-1)+…+f(2)+f(1)
=
[f(n-1)+1]+[f(n-2)+1]+…+[f(1)+1]+[1]
即得到：
f(n)=n
已經(jīng)有那么點(diǎn)意思了哈，再來(lái)個(gè)復(fù)雜點(diǎn)的算法。
案例二：二分查找binary_search，時(shí)間復(fù)雜度分析。
int BS(int[] arr, int low, int high, int target){
? ? ? ???if (low>high) return -1;
? ? ? ???mid = (low+high)/2;
? ? ? ???if (arr[mid]== target) return mid;
? ? ? ???if (arr[mid]> target)
? ? ? ???? ? ? ???return BS(arr, low, mid-1, target);
? ? ? ???else
? ? ? ???? ? ? ???return BS(arr, mid+1, high, target);
}
二分查找，單純從遞歸算法來(lái)分析，怎能知道其時(shí)間復(fù)雜度是O(lg(n))呢？
仍用f(n)來(lái)表示數(shù)據(jù)量為n時(shí)，算法的計(jì)算次數(shù)，很容易知道：
當(dāng)n=1時(shí)，bs函數(shù)只計(jì)算1次
畫外音：不用糾結(jié)是1次還是1.5次，還是2.7次，是一個(gè)常數(shù)次。
即：
f(1)=1【式子A】
在n很大時(shí)，二分會(huì)進(jìn)行一次比較，然后進(jìn)行左側(cè)或者右側(cè)的遞歸，以減少一半的數(shù)據(jù)量：
f(n)的計(jì)算次數(shù)，等于f(n/2)的計(jì)算次數(shù)，再加1次計(jì)算
畫外音：計(jì)算arr[mid]>target，再減少一半數(shù)據(jù)量迭代
即：
f(n)=f(n/2)+1【式子B】
【式子B】不斷的展開(kāi)，
f(n)=f(n/2)+1
f(n/2)=f(n/4)+1
f(n/4)=f(n/8)+1
…
f(n/2^(m-1))=f(n/2^m)+1
上面共m個(gè)等式，左側(cè)和右側(cè)分別相加：
f(n)+f(n/2)+…+f(n/2^(m-1))
=
[f(n/2)+1]+[f(n/4)+1]+…+[f(n/2^m)]+[1]
即得到：
f(n)=f(n/2^m)+m
再配合【式子A】：
f(1)=1
即，n/2^m=1時(shí), f(n/2^m)=1, 此時(shí)m=lg(n), 這一步，這是分析這個(gè)算法的關(guān)鍵。
將m=lg(n)帶入，得到：
f(n)=1+lg(n)
神奇不神奇？
最后，大boss，快速排序遞歸算法，時(shí)間復(fù)雜度的分析過(guò)程。
案例三：快速排序quick_sort，時(shí)間復(fù)雜度分析。
void quick_sort(int[]arr, int low, inthigh){
? ? ? ? ?if (low==high) return;
? ? ? ? ?int i = partition(arr, low, high);
? ? ? ? ?quick_sort(arr, low, i-1);
? ? ? ? ?quick_sort(arr, i+1, high);
}
仍用f(n)來(lái)表示數(shù)據(jù)量為n時(shí)，算法的計(jì)算次數(shù)，很容易知道：
當(dāng)n=1時(shí)，quick_sort函數(shù)只計(jì)算1次
f(1)=1【式子A】
在n很大時(shí)：
第一步，先做一次partition；
第二步，左半?yún)^(qū)遞歸；
第三步，右半?yún)^(qū)遞歸；
即：
f(n)=n+f(n/2)+f(n/2)=n+2*f(n/2)【式子B】
畫外音：
(1)partition本質(zhì)是一個(gè)for，計(jì)算次數(shù)是n；
(2)二分查找只需要遞歸一個(gè)半?yún)^(qū)，而快速排序左半?yún)^(qū)和右半?yún)^(qū)都要遞歸，這一點(diǎn)在分治法與減治法一章節(jié)已經(jīng)詳細(xì)講述過(guò)；
【式子B】不斷的展開(kāi)，
f(n)=n+2*f(n/2)
f(n/2)=n/2+2*f(n/4)
f(n/4)=n/4+2*f(n/8)
…
f(n/2^(m-1))=n/2^(m-1)+2f(n/2^m)
上面共m個(gè)等式，逐步帶入，于是得到：
f(n)=n+2*f(n/2)
=n+2*[n/2+2*f(n/4)]=2n+4*f(n/4)
=2n+4*[n/4+2*f(n/8)]=3n+8f(n/8)
=…
=m*n+2^m*f(n/2^m)
再配合【式子A】：
f(1)=1
即，n/2^m=1時(shí), f(n/2^m)=1, 此時(shí)m=lg(n), 這一步，這是分析這個(gè)算法的關(guān)鍵。
將m=lg(n)帶入，得到：
f(n)=lg(n)*n+2^(lg(n))*f(1)=n*lg(n)+n
故，快速排序的時(shí)間復(fù)雜度是n*lg(n)。
wacalei，有點(diǎn)意思哈！
畫外音：額，估計(jì)83%的同學(xué)沒(méi)有仔細(xì)看，花5分鐘細(xì)思上述過(guò)程，一定有收獲。
總結(jié)
for循環(huán)的時(shí)間復(fù)雜度往往是O(n)
樹(shù)的高度的時(shí)間復(fù)雜度往往是O(lg(n))
二分查找的時(shí)間復(fù)雜度是O(lg(n))，快速排序的時(shí)間復(fù)雜度n*(lg(n))
遞歸求解，未來(lái)再問(wèn)時(shí)間復(fù)雜度，通殺
知其然，知其所以然。思路比結(jié)論重要。
架構(gòu)師之路-分享可落地的技術(shù)文章
相關(guān)文章：
謝轉(zhuǎn)。