[TOC] ## 算法復雜度 1. 如果計算的速度越快，那么這個算法時間復雜度越低。 2. 如果占用的計算資源越少，那么空間復雜度越低。 算法的優先級排列如下，一般排在上面的要優于排在下面的： 1. 常數復雜度：`O(1)` 2. 對數復雜度：`O(logn)` 3. 一次方復雜度：`O(n)` 4. 一次方乘對數復雜度：`O(nlogn)` 5. 乘方復雜度：`O(n^2)`，`O(n^3)` 6. 指數復雜度：`O(2^n)` 7. 階乘復雜度：`O(n!)` 8. 無限大指數復雜度：`O(n^n)` ## 計算復雜度 計算公式`1 + 2 + 3 + ... + 100` ### demo1 ``` package main import "fmt" func sum(n int) int { total := 0 // 從1加到N, 1+2+3+4+5+..+N for i := 1; i <= n; i++ { total = total + i } return total } func main() { fmt.Println(sum(100)) } ``` 因為要循環計算 n-1 次，而當 n 無限大時，常數項基本忽略不計，所以這個算法的時間復雜度，我們用 O(n) 來表示 ### demo2 ``` func sum2(n int) int { total := ((1 + n) * n) / 2 return total } ``` 這次算法只需執行 1 次，所以這個算法的時間復雜度是 O(1)。可以看出，時間復雜度為 O(1) 的算法優于復雜度為 O(n) 的算法 ## 遞歸函數的復雜度  ### 二分法復雜度 1. 二分搜索，每次問題規模減半，只查一個數，遞推過程之外的查找復雜度為`O(1)`，遞推運算時間公式為：`T(n) = T(n/2) + O(1)`。 2. 快速排序，每次隨機選一個數字作為劃分進行排序，每次問題規模減半，遞推過程之外的排序復雜度為`O(n)`，遞推運算時間遞推公式為：`T(n) = 2T(n/2) + O(n)`。 按照簡化版的主定理，可以知道： 二分查找：`a = 1，b = 2，d = 0`，可以知道`a = b^d`，所以二分查找的時間復雜度為：`O(logn)`。 快速排序：`a = 2，b = 2，d = 1`，可以知道`a = b^d`，所以快速排序的時間復雜度為：`O(nlogn)`。 強調：并非所有遞推關系式都可應用主定理，但是大部分情況下都可以。