[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) 的算法 ## 递归函数的复杂度 ![UTOOLS1588060549551.png](http://yanxuan.nosdn.127.net/85296f46c0e9a5416c708af4b8e1f565.png) ### 二分法复杂度 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)`。 强调:并非所有递推关系式都可应用主定理,但是大部分情况下都可以。