時間複雜度的分析及排序算法總結

時間複雜度

當問題規模即要處理的數據增⻓時，基本操作要重複執⾏的次數必定也會增⻓，那麼我們關⼼地是這個執⾏次數以什麼樣的數量級增⻓。

算法時間複雜度是一個函數，它定性描述該算法的運行時間（也就是所花費時間的消耗）。

我們要知道討論的時間複雜度就是指一般情況下的時間複雜度。

表示法

我們⽤⼤O表示法表示⼀下常⻅的時間複雜度量級：

常數階O(1) 線性階O(n) 對數階O(logn) 線性對數階O(nlogn) 平⽅階O(n²)。

排序算法中各個算法時間複雜度為：O(n2), O(nlogn), O(n)。這些我們之前都學習過，可以先從排序算法來理解時間複雜度。這裡所說的都是指的一般情況下的時間複雜度（或者平均時間複雜度）。

當然還有指數階和階乘階這種⾮常極端的複雜度量級，我們就不討論了。

O(1)

傳說中的常數階的複雜度，這種複雜度⽆論數據規模n如何增⻓，計算時間是不變的。不管n如何增⻓，都不會影響到這個函數的計算時間，因此這個代碼的時間複雜度都是O(1)。

O(n)

線性複雜度，隨著數據規模n的增⻓，計算時間也會隨著n線性增⻓。典型的O(n)的例⼦就是線性查找。

const linearSearch = (arr, target) => {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
}

線性查找的時間消化與輸⼊的數組數量n成⼀個線性⽐例，隨著n規模的增⼤，時間也會線性增⻓。

注意：下面代碼的時間複雜度也是O(n)。

O(n + n) = O(2n) = O(n)。

const search = (arr) => {
for (let i = 0; i < arr.length; i++) {
...
}

for (let i = 0; i < arr.length; i++) {
...
}

return -1;
}

O(logn)

對數複雜度，隨著問題規模n的增⻓，計算時間也會隨著n對數級增⻓。

典型的例⼦是⼆分查找法（有序序列）。

functions binarySearch(arr, target) {
let max = arr.length - 1；
let min = 0；

while (min <= max) {
let mid = Math.floor((max + min) / 2)；
if (target < arr[mid]) {
max = mid - 1；
} else if (target > arr[mid]) {
min = mid + 1；
} else {
return mid；
}
}
return -1
}

在⼆分查找法的代碼中，通過while循環，成 2 倍數的縮減搜索範圍，也就是說需要經過 log2n 次即可跳出循環。

事實上在實際項⽬中， O(logn) 是⼀個⾮常好的時間複雜度，⽐如當 n=100 的數據規模時，⼆分查找只需要7次，線性查找需要100次，這對於計算機⽽⾔差距不⼤，但是當有10億的數據規模的時候，⼆分查找依然只需要30次，⽽線性查找需要驚⼈的10億次， O(logn) 時間複雜度的算法隨著數據規模的增⼤，它的優勢就越明顯。

O(nlogn)

線性對數複雜度，隨著數據規模n的增⻓，計算時間也會隨著n呈線性對數級增⻓。

這其中典型代表就是歸併排序，快速排序，堆排序，希爾排序。

以堆排序為例：

堆排序中有兩個步驟：

創建堆：

調整堆

O(n²)

平⽅級複雜度，典型情況是當存在雙重循環的時候，即把 O(n) 的代碼再嵌套循環⼀遍，它的時間複雜度就是 O(n²)了，代表應⽤是冒泡排序，插入排序，簡單選擇排序。

注意：要理解時間複雜度本質，不能單純的記憶兩個for循環的時間複雜度是O(n2)，三個for循環的時間複雜度是O(n3)，還要看for循環的數量級。例如希爾排序，是三個for循環，但是它的時間複雜度是O(nlogn)。

關於logn思考

logn指的是n的對數，在數學中，n的對數必須有底數，也就是像log2n，log3n...。

那時間複雜度中的logn是以幾為底數呢？

有人說logn的底數為2，這種理解非常的片面，可以說是很不準確的，說明還沒有理解時間複雜度所要表達的本質是什麼。看了一些文檔，但是並沒有看到一篇好的文章去說明，或者探討清楚這個問題。實際上無論以2，或3為底數，其實這些都是常量，並不影響我們用logn來表述算法的時間複雜度，就像兩個n數量級的for循環一樣，並不是O(2n)，而是O(n)。所以，我們統一說是O(logn)，也就是忽略了底數的描述。

推導：(以2，和10為例)

n = 10 log10n

log2n = log10n * log210

log2n  => log10n

遞歸算法的時間複雜度

相信很多同學對遞歸算法的時間複雜度都很模糊。

「同一道題目，同樣使用遞歸算法，有的同學會寫出了O(n)的代碼，有的同學就寫出了O(logn)的代碼」。

這是為什麼呢？如果對遞歸的時間複雜度理解的不夠深入的話，就會這樣！遞歸代碼看起來很簡介，優雅，但理解起來不是很透徹，包括我有些地方也不是很透徹，那在使用的過程中就更不容易用好遞歸了。

一個例子，來帶大家逐步分析遞歸算法的時間複雜度，最後找出最優解，來看看同樣是遞歸，怎麼就寫成了O(n)的代碼。

求x的n次方

function func1(x, n) {
let result = 1; // 注意 任何數的0次方等於1
for (let i = 0; i < n; i++) {
result = result * x;
}

return result;
}

上面的代碼的時間複雜度為O(n)，怎麼能把上面的代碼優化一下，降低時間複雜度呢？

用遞歸實現

function func2(x, n) {
if(n == 0){
return 1;
}

return x * func2(x, n-1);
}

遞歸算法的時間複雜度本質上是要看: 「遞歸的次數 * 每次遞歸中的操作次數」。

所以上面代碼的時間複雜度是 O(n)，並沒有得到優化。

另一種遞歸實現

function func3(x, n){
if(n== 0) {
return 1;
}
if(n % 2 === 1) {
let n1 = Math.floor(n/2);
return func3(x, n1) * func3(x, n1) * x;
}
return func3(x, n/2) * func3(x, n/2);
}

我們來分析一下，首先看遞歸了多少次呢，可以把遞歸抽象出一顆滿二叉樹。剛剛同學寫的這個算法，可以用一顆滿二叉樹來表示（為了方便表示，選擇n為偶數16），如圖：

這棵樹上每一個節點就代表著一次遞歸併進行了一次相乘操作，所以進行了多少次遞歸的話，就是看這棵樹上有多少個節點。

熟悉二叉樹話應該知道如何求滿二叉樹節點數量，這顆滿二叉樹的節點數量就是2^3 + 2^2 + 2^1 + 2^0 = 15，可以發現：「這其實是等比數列的求和公式，這個結論在二叉樹裡也經常出現」。

這麼如果是求x的n次方，這個遞歸樹有多少個節點呢？

「時間複雜度忽略掉常數項-1之後，這個遞歸算法的時間複雜度依然是O(n)」。對，你沒看錯，依然是O(n)的時間複雜度！

看來還是沒有得到優化啊。返回看func3中存在很多重複的遞歸計算，可以從這個點進行優化。

第三種遞歸實現

function func4(x, n){
if(n== 0) {
return 1;
}
let t = func4(x, Math.floor(n/2));
if(n % 2 === 1) {
return t * t * x;
}
return t * t;
}

依然還是看他遞歸了多少次，可以看到這裡僅僅有一個遞歸調用，且每次都是n/2 ，所以這裡我們一共調用了log以2為底n的對數次。

所以，上面的算法時間複雜度為O(logn).

同樣使用遞歸，有的人可以寫出O(logn)的代碼，有的人還是可以寫出O(n)的代碼。

相信大家對遞歸算法的有一個新的認識的，同一個問題，同樣是遞歸，效率可是不一樣的！

還能不能再優化呢？就是想讓遞歸的執行時間縮短！！

第四種遞歸實現

function func5(x, n, res){
if(n == 1) {
return res;
}
return func5(x, n-1, res*x);
}

上面的遞歸實現，代碼簡潔了很多，可讀性也好了很多，但是看不出來性能哪裡好了？執行時間呢？

下面將第三種遞歸和第四種遞歸做一個執行時間的對比：

function func4(x, n){
if(n== 0) {
return 1;
}
let t = func4(x, Math.floor(n/2));
if(n % 2 === 1) {
return t * t * x;
}
return t * t;
}
function func5(x, n, res){
if(n == 1) {
return res;
}
return func5(x, n-1, res*x);

}

console.time();

console.log(func4(2, 100));

console.timeEnd();

console.time();

console.log(func5(2, 100, 2));

console.timeEnd();

我地個天啊，差距怎麼這麼大啊！！最後一種遞歸的實現怎麼竟然可以這麼的優秀！！！這個會在我的另一篇文章中招到答案。

至此，希望大家對時間複雜度有一個初步的理解和認識。

排序算法總結排序算法比較

排序算法的選擇

不同算法的時間複雜度 在不同數據輸入規模下的差異。

我們在決定使用那些算法的時候 ，不是時間複雜越低的越好，要考慮數據規模，如果數據規模很小可以用O(n^2)的算法。

就像上圖中圖中 O(5n^2) 和 O(100n) 在n為20之前 很明顯 O(5n^2)是更優的，所花費的時間也是最少的。

這也就是為什麼JS中自帶排序方法 Array.sort在數據量小的情況下，選擇插入排序的原因。