[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)`。 强调：并非所有递推关系式都可应用主定理，但是大部分情况下都可以。