算法复杂度及渐进符号
最后更新于：2022-04-02 04:10:48
[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)`。
强调：并非所有递推关系式都可应用主定理，但是大部分情况下都可以。
';