數據結構與算法看完了，回過頭來在看時間復雜度，對它們的效率做個比較吧。

一、時間復雜度介紹

1、時間復雜度定義

參看：數據結構-算法-時間復雜度計算

在進行算法分析，語句總得執行次數 T(n) 是關于問題規模 n 的函數，進而分析 T(n) 隨 n 的變化情況并確定 T(n) 數量級。算法的時間復雜度，也就是算法的時間量度，記作：T(n) = O(f(n))，它表示隨問題規模 n 的增大算法執行時間的增長率和 f(n) 的增長率相同，稱作算法的漸近時間復雜度，簡稱為時間復雜度，其中 f(n) 是問題規模 n 的某個函數。

2、求解時間復雜度具體步驟

（1）找出算法中的基本語句 算法中執行次數最多的那條語句就是基本語句，通常是最內層循環的循環體。 （2）計算基本語句的執行次數的數量級 只需計算基本語句執行次數的數量級，這就意味著只要保證基本語句執行次數的函數中的最高次冪正確即可。可以忽略所有低次冪和最高次冪的系數。這樣能夠簡化算法分析，并且使注意力集中在最重要的一點上：增長率。 （3）用大 O 記號表示算法的時間性能 將基本語句執行次數的數量級放入大 O 記號中。 大 O 中的 O 的意思就是"order of"（大約是），它是種概念，就比如 大型車、小型車和中型車，忽略具體大小尺寸，來描述汽車。

3、時間復雜度計算方法

（1）用常數 1 取代運行時間中的所有加法常數。 （2）在修改后的運行次數函數中，只保留最高階項。 （3）如果最高階存在且不是 1，則去除與這個項相乘的常數。最后，得到的最后結果就是時間復雜度。 簡單來說，就是保留求出次數的最高次冪，并且把系數去掉，如 T(n) = 2n^2+n+1 = O(n^2)

4、常見的時間復雜度

（1）常數級復雜度：O(1)
（2）對數級復雜度：O(logN)
（3）線性級復雜度：O(N)
（4）線性對數級復雜度：O(NlogN)
（5）平方級復雜度：O(N^2)

復雜度曲線越平越好，越陡越差，常數級復雜度最為理想。 常用的時間復雜度所耗費的時間從小到大依次是： O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
舉例說明：

執行次數函數	階	非正式術語
12	O(1)	常數階
5log2^n + 20	O(logn)	對數階
2n + 3	O(n)	線性階
2n + 3nlog2^2 + 19	O(nlogn)	線性對數階
3n^2 + 2n + 1	O(n^2) ? ?	平方階
6n^3 + 2n^2 + 3n + 4 ? ?	O(n^3)	立方階
2^n	O(2^n)	指數階

二、具體說明各種時間復雜度

按照時間復雜度從小到大依次講解： 講解之前需要了解一個概念：頻度 參看：數據結構頻度 在數據結構中，頻度是指一個定義變量在它的函數中，并且是它在執行到該段語句為止時，這個定義變量在函數總共執行基本操作的次數。 例如下函數中各行頻度n的計算： for(i=0;i<n;i++) ----------------------------- (1) {for(j=0;j<n;j++) ------------------------- (2){c[i][j]=0; ------------------------------ (3)for(k=0;k<n;k++) ------------------- (4){c[i][j]=c[i][j]+a[i][k]*b[k][j]; ------- (5)}} }（1） for(i=0;i<n;i++) ?頻度為： n+1
（2） for(j=0;j<n;j++) ?頻度為：n*(n+1)
（3） c[i][j]=0 ?頻度為：n*n
（4） for(k=0;k<n;k++) ?頻度為：n*n*(n+1)
（5） c[i][j]=c[i][j]+a[i][k]*b[k][j] ?頻度為：n*n*n
解釋： （1）i 變量在第一個 for 循環中，從取 i = 0 開始執行，直到i=n-1時為止，至此，i 執行了n次。加上最后i=n跳出循環的判斷，故頻度共n+1 次；
（2）與（1）不同，當 i 在 0~(n-1) 范圍內，內層循環 [即是（2）的for循環] 頻度為 n ； 當 i = n 時，內層循環語句沒執行。所以相當此時第（1）中 for 循環執行了n次，第二個for 循環執行了n次，加上最后j=n跳出循環的判斷，即，頻度共 n * (n+1)；
（3）此句語句，是要利用（1）、（2）for循環語句的i ,j 對 c[i][j] 進行賦值，此時，i 得到的賦值只有從 0 到 n , j 得到的賦值也是從0到n ,都是 n次，此時（當 i 達到n-1 .\當 j 達到 n-1.）的 i++ \j++都不會執行。 故，頻度共 n*n 次；
（4）同上（1），（2）的理由，單獨的（4）的for 循環執行了n+1 次，綜上，頻度為 n*n*(n+1)；
（5）同理（3），對于三個for 循環， i 得到的賦值只有從 0 到 n , j 得到的賦值也是從0到n ,k得到的賦值也是從 0 到 n ,即，頻度為n*n*n。

1、常數階（O(1)）

#include <stdio.h>int main (void) {int n = 10;printf ("n = %d\n", n);printf ("n = %d\n", n);printf ("n = %d\n", n);printf ("n = %d\n", n);printf ("n = %d\n", n);printf ("n = %d\n", n);printf ("n = %d\n", n);printf ("n = %d\n", n);return 0; } 分析： 上述代碼中，每條語句的頻度均為 1，即 T(n) = O(9)，但是一般記作 O(1)。因此它的時間復雜度為 O(1)

（2）對數階（O(logn)）

#include <stdio.h>int main (void) {int i = 1, n = 1000; //語句1while (i < n) i = i*2; //語句2return 0; } 分析：語句1頻度為：1語句2頻度為：f(n)，則2^f(n)<=n；f(n)<=log₂n ?取最大值 f(n)= log₂n即T(n) =?log₂n + 1 =?O(log₂n )，因此它的時間復雜度為 O(logn)

（3）線性階（O(n)）

#include <stdio.h>int main (void) {int i = 0, sum = 0, n = 10; //語句1for (i = 0; i < n; i++) //語句2sum += i; //語句3printf ("sum = %d\n", sum); //語句4 return 0; } 輸出結果： sum = 45 分析：語句1頻度為：1語句2頻度為：n+1語句3頻度為：n語句4頻度為：1即T(n) = 1 + (n + 1) + n + 1 = 2n + 3 = O(n)，因此它的時間復雜度為O(n)

（4）線性對數階（O(nlongn)）

#include <stdio.h> void quick (int arr[], int left, int right) { int p = (left + right) / 2; int pivot = arr[p]; int i = 0, j = 0; for(i = left, j = right; i < j;) { while (arr[i] < pivot && i < p) i++; if (i < p) { arr[p] = arr[i]; p = i;} while(arr[j] >= pivot && j > p) j--; if (j > p) { arr[p] = arr[j]; p = j; } arr[p] = pivot; if(p - left > 1) quick (arr, left, p - 1); if (right - p > 1) quick (arr, p + 1, right); } } int main() { int arr[9] = {20, 8, 25, 3, 15, 9, 30, 5, 22}; quick (arr, 0, 8); int i = 0; for(i = 0; i < 9; i++) printf ("%d ", arr[i]); printf ("\n"); return 0; } 輸出結果： 3 5 8 9 15 20 22 25 30 分析：上述例子為快速排序，如果每次都是均等的劃分即T(n)=T(n/2)+T(n/2)+O(n)，即每次分成兩段，則分的次數為logn，每一次處理需要n次計算，那么時間復雜度就是nlogn如果每次的劃分都是完全不平衡的即T(n)=T(n-1)+O(n)，那么快排的時間復雜度是n^2所以它是不穩定的，因此我們說?快排的平均時間復雜度是nlogn

（5）平方階（O(n^2)）

#include <stdio.h> int main (void) { int i, j, n = 10; //語句1for (i = 0;i < n; i++) //語句2{for (j = 0; j < n; j++) //語句3printf ("*"); printf ("\n"); }return 0; } 分析：語句1頻度為：1語句2頻度為：n + 1語句3頻度為 n * (n + 1)即T(n) = 1 + (n + 1) + n * (n + 1) = n^2 + 2n + 2 = O(n^2)，因此它的時間復雜度為 O(N^2)

（6）立方階（O(n^3)）

#include <stdio.h> int main (void) { int i, j, k, n = 3; //語句1for (i = 0;i < n; i++) //語句2{for (j = 0; j < n; j++) //語句3{for (k = 0; k < n; k++) //語句4printf ("*");printf ("\n");}}return 0; } 分析： 語句1頻度為：1 語句2頻度為：n + 1 語句3頻度為：n * (n + 1) 語句4頻度為：n * n * (n + 1) 即T(n) = 1 + (n + 1) + n * (n + 1) + n * n * (n + 1) = n^3 + 2n^2 + 2n + 2 = O(n^3) 因此它的時間復雜度為 O(n^3)

（7）指數階（O(2^n)）

#include <stdio.h> int i = 1;void move (int n, char from, char to) { printf ("第%d步:將%d號盤子%c---->%c\n", i++, n, from, to); //語句1 } void hanoi (int n, char from, char denpend_on, char to) { if (n == 1) move (1, from, to); else { hanoi (n - 1, from, to, denpend_on); move (n, from, to); hanoi (n - 1, denpend_on, from, to); } } int main (void) { printf ("請輸入盤子的個數:\n"); int n; scanf ("%d", &n); char x = 'A', y = 'B', z = 'C'; printf ("盤子移動情況如下:\n"); hanoi (n, x, y, z); } 分析：語句1頻度為：1?因此，當 if (n == 1) 時， T(n) = 1 = O(1)否則，T(n) = 2T(n - 1) + 1 = 2^n + 1 = O(2^n) ?因此它的時間復雜度為 O(2^n)相關遞推公式就不寫了，寫了也看不懂。

三、常用數據結構和算法的時間復雜度

參看：常用數據結構和算法操作效率的對比總結

1、數據結構部分

數據結構中常用的操作的效率表

通用數據結構	查找?	插入?	?刪除	遍歷?
數組	O(N)	O(N)	O(N)	—
有序數組	O(logN)	O(N)	O(N)	O(N)
鏈表	O(N)	O(1)	O(N)	—
有序鏈表	O(N)	O(N)	O(N)	O(N)
二叉樹	O(logN)	O(logN)	O(logN)	O(N)
二叉樹（最壞）	O(N)	O(N)	O(N)	O(N)
紅黑樹	O(logN)	O(logN)	O(logN)	O(N)
2-3-4樹	O(logN)	O(logN)	O(logN)	O(N)
哈希表	O(1)	O(1)	O(1)	—
專用數據結構	?	?	?	?
棧	—	O(1)	O(1)	—
隊列	—	O(1)	O(1)	—
優先級隊列	—	O(N)	O(1)	—
優先級隊列（堆）	—	O(logN)	O(logN)	?

2、排序部分

常見的排序算法比較表

排序	平均情況	最好情況	最壞情況	穩定與否	空間復雜度
冒泡排序	O(N2)	O(N)	O(N2)	穩定	1
選擇排序	O(N2)	O(N2)	O(N2)	不穩定	1
插入排序	O(N2)	O(N)	O(N2)	穩定	1
希爾排序	O(NlogN)	（依賴于增量序列）		不穩定	1
快速排序	O(NlogN)	O(NlogN)	O(N2)	不穩定	O(logN)
歸并排序	O(NlogN)	O(NlogN)	O(NlogN)	穩定	O(N)
二叉樹排序	O(NlogN)	O(NlogN)	O(N2)	穩定	O(N)
堆排序	O(NlogN)	O(NlogN)	O(NlogN)	不穩定	1
拓撲排序	O(N+E)	—	—	—	O(N)

3、平均和最壞時間復雜度

（1）最壞時間復雜度 顧名思義，時間復雜度不能再壞了。 以快排為例，在最壞情況下的時間復雜度為T(n) = O(n^2)，它表示對于任何輸入實例，該算法的運行時間不可能大于0(n^2) （2）平均時間復雜度 平均時間復雜度是指所有可能的輸入實例均以等概率出現的情況下。
還以快排為例，如果每次均等劃分，如果每次都是均等的劃分即T(n)=T(n/2)+T(n/2)+O(n)，即每次分成兩段，則分的次數為logn，每一次處理需要n次計算，那么時間復雜度就是nlogn。如果每次的劃分都是完全不平衡的即T(n)=T(n-1)+O(n)，那么快排的時間復雜度是n^2。但它是不穩定的，無法確保它是否均等劃分，因此我們說快排的平均時間復雜度是nlogn。

四、時間復雜度和實際運行時間

時間復雜度和實際運行時間不是一碼事，我們在計算時間復雜度的時候，是忽略所有低次冪和最高次冪的系數的。 比如有一個算法，輸入n個數據，經過3n^2+log2(n)+n+5次計算得到結果，其時間復雜度為O(n^2)。另外一個算法只需2n^2次計算就能得到結果，其時間復雜度也是O(n^2)，但明顯比第一個算法要快。 所以說時間復雜度是可以推演計算的，而實際運算時間不可預測。這也是為什么使用時間復雜度而不是使用實際運算時間來判斷一個算法的優劣了。

總結

以上是生活随笔為你收集整理的数据结构与算法 -- 时间复杂度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。