2.1 算法復雜度 · 計算機基礎知識

## 算法的時間復雜度和空間復雜度 > 程序 = 算法 + 數據結構【目錄】 --- [TOC] --- ### 時間復雜度 > 指的是算法的時間耗費。在算法的每個步驟中，可能有若干條語句，而頻度就是指每條語句的執行次數。簡單來說，以一條基本語句的執行時間為基本單位，該算法所有語句中總的基本語句的執行次數就是該算法的時間耗費，它是該算法所求解的問題規模 ` n ` 的函數。當問題的規模`n`趨向無窮大時，我們就把時間復雜度的數量階稱為算法的漸進時間復雜度。一般我們把漸進時間復雜度稱為算法的時間復雜度，記作“O”(Order)，它有嚴格的數學意義：若`T(n)`和`f(n)`是定義在正整數集合的兩個函數，則`T(n)=O(f(n))`表示存在正常的常數`C`和`n0`，使得當` n ≥ n0 `時都滿足` 0 ≤ T(n) ≤ C * f(n)`。各個時間復雜度大小關系： $$ O(1) < O(\log_2n) < O(n) < O(n\log_2 n) < O(n^2) < O(n^3) < O(2^n) < O(n^n) < O(n!) $$ > 常數階 O(1) 算法中語句執行次數為常數，則時間復雜度為`O(1)` ```java int i = 1;// 頻度1 i++;// 頻度1 // 頻度總和是一個常數 ``` > 對數階 O(log_2n) ```java public int calc(int number) { int return_number = 1;// 頻度1 while(return_number <= number) { return_number = return_number * 2;// 假設頻度是 f(n) , 2^f(n) ≤ n; f(n) ≤ log2n } return return_number; } // 總和： log2n + 1 ，所以 T(n) = O(log2n) ``` > 線性階 O(n) ```java public int calc(int number) { int a = 0;// 頻度1 while(number > 0) { a += numer;// 頻度 n number--;// 頻度 n } return a; } // 頻度總和：2n + 1，所以 T(n) = O(n) ``` > 線性對數階O(nlog_2 n) > > 結合 n 和 log2n > 平方階O(n^2) > > eg：2個for循環 > 立方階O(n^3) > > eg：3個for循環 > k次方階O(n^k) > > eg：n個循環 > 指數階O(n^n) > > eg：n維數組 #### 【常見排序算法時間復雜度】 | 算法 | 平均時間 | 最差情形 | 穩定度 | 額外空間 | 備注 | | :---: | :------: | :----------: | :----: | :------: | :-----------------------------------: | | 冒泡 | O(n^2) | O(n^2) | 穩定 | O(1) | n較小時，較好 | | 交換 | O(n^2) | O(n^2) | 不穩定 | O(1) | n較小時，較好 | | 選擇 | O(n^2) | O(n^2) | 不穩定 | O(1) | n較小時，較好 | | 插入 | O(n^2) | O(n^2) | 穩定 | O(1) | 大部分已排序時較好 | | 基數 | O(logRB) | O(logRB) | 穩定 | O(n) | B是真數0-9 R是基數（個，十，百） | | Shell | O(nlogn) | O(n^s) 1<s<2 | 不穩定 | O(1) | s是所選分組 | | 快速 | O(nlogn) | O(n^2) | 不穩定 | O(nlogn) | n大時較好 | | 歸并 | O(nlogn) | O(nlogn) | 穩定 | O(1) | n大時較好 | | 堆 | O(nlogn) | O(nlogn) | 不穩定 | O(1) | n大時較好 | #### 【經驗規則】 - 其中c是一個常量，如果一個算法的復雜度為c 、 log\*2n 、n 、 nlog2n,那么這個算法時間效率比較高 - 如果是2^n ,3^n ,n!，那么稍微大一些的n就會令這個算法不能動了，居于中間的幾個則差強人意。 #### 【求算時間復雜度具體步驟】 - 找出算法中的基本語句 - 通常是內層循環的循環體 - 計算基本語句的執行次數的數量級 - 保證基本語句執行次數的最高次冪正確，可以忽略低次冪和最高次冪的系數，集中注意力到最重要的一點上：增長率。 - 用大O記號表示算法的時間性能 #### 【分析法則】 - 一些簡單的輸入輸出語句或賦值語句,近似認為需要O(1)時間 - 順序結構,需要依次執行一系列語句所用的時間可采用大O下"求和法則" **求和法則**:是指若算法的2個部分時間復雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1(n)+T2(n)=O(max(f(n), g(n))) 特別地,若T1(m)=O(f(m)), T2(n)=O(g(n)),則 T1(m)+T2(n)=O(f(m) + g(n)) - 選擇結構,如if語句,它的主要時間耗費是在執行then字句或else字句所用的時間,需注意的是檢驗條件也需要O(1)時間 - 循環結構,循環語句的運行時間主要體現在多次迭代中執行循環體以及檢驗循環條件的時間耗費,一般可用大O下"乘法法則" **乘法法則**: 是指若算法的2個部分時間復雜度分別為 T1(n)=O(f(n))和 T2(n)=O(g(n)),則 T1*T2=O(f(n)*g(n)) - 對于復雜的算法,可以將它分成幾個容易估算的部分,然后利用求和法則和乘法法則技術整個算法的時間復雜度另外還有以下2個運算法則:(1) 若g(n)=O(f(n)),則O(f(n))+ O(g(n))= O(f(n))；(2) O(Cf(n)) = O(f(n)),其中C是一個正常數 #### 【例子】 1、 ```java for (int i=0; i<n; i++){// 執行 n+1 次 for (int j=0; j<n; j++) {// n*(n+1) x = x + 1; // n*n } } ``` 總的次數：n+1 + n*(n+1) + n * n = 2n^2 + 2n + 1，當 n 趨向于無窮大的時候，其執行的次數和 n^2 是同一個數量階，所以時間復雜度是 O(n^2) 2、 ```php for (int $i=0; i<1000; $i++){// 執行 1001 次 for (int $j=0; $j<1000; $j++) {// 1000*1001 $x = $x + 1; // 1000 * 10000 } } ``` 總的次數是一個常數，與常數同階，時間復雜度是O(1) 3、在一個有序的數組中查找關鍵字K。 - 二分查找（折半查找）無論是K 處于前半部分，還是后半部分，都是忽略另外一部分，直到找到關鍵字K（或者沒有在數組中），這個過程至多重復 log2n 次 ```java static int binarySearch(int K, int[] array, int left, int right) { int l = left - 1; int r = right + 1; while(l+1 != r) { int i = (l+r)/2; if (K < array[i]) { r = i; } if (K == array[i]) { return i; } if (K > array[i]) { l = i; } } return -1; } ``` 【參考鏈接】 [算法的時間復雜度和空間復雜度-總結](https://blog.csdn.net/zolalad/article/details/11848739) ### 空間復雜度 > 該算法所耗費的空間，也是問題規模 n 的函數。一般是指漸進空間復雜度。記作：S(n) = O(f(n)) 例子： 1、一個包含了 n 個整數的一維數組空間代價是多少？ - 如果每個整數占有 c 個字節空間，則整個數組占用 cn 個字節空間，其空間復雜度就是 O(n)。 - 在存儲結構中，例如指針實際上是附加信息的開銷，稱為結構性開銷。理論上來說，結構性開銷應該盡量小，而訪問路徑又應該盡可能的多且有效。 2、信息壓縮和解壓縮 ### 【總結】 - 算法分析時，除非特別聲明，都是按照最壞情況分析。我們通常所說的算法的復雜度一般是時間復雜度和空間復雜度的合稱。 - 解決問題的步驟應該是：先調整算法，后調整代碼。