1. 前言
在深入学习前,这些知识点要先知道,下面就让我们学习起来。
2. 参考资料
3. 时间频度
时间频度是一个算法中的语句执行的次数。记为 T(n)。
当T(n)在一些场景下可以:忽略常数项、忽略低次项、忽略系数
忽略常数项
如:T(n)=3n+2,当n趋向无穷大时,可以忽略常数项2;
忽略低次项
如:T(n)=3n+5n^8,当n趋向无穷大时,可以忽略低次项及其系数3n;
忽略系数
如:T(n)=3n^6,当n趋向无穷大时,可以忽略系数3。
4. 时间复杂度
算法的时间复杂度(Time complexity)是一个函数,它用于描述算法执行的时间,用大O符号表述。
时间复杂度和时间频度关系
假设当有一个辅助函数f(n),使得当n趋近无穷大时,T(n)/f(n)的极限值为不等于0的常数,就叫f(n)为T(n)的同量级函数,记作T(n)=O(f(n)),称O(f(n))为算法的时间渐进复杂度,也就是时间复杂度。
4.1. 推导时间复杂度
根据时间频度T(n)的“三个忽略”原则,可知时间复杂度的特点:
- 忽略所有常数
- 只保留函数中的最高阶项
- 去掉最高阶项的系数
一般求解步骤:
- 找基本语句,通常是最内层循环的循环体。
- 计算基本语句的执行次数的数量级。
- 将基本语句执行次数的数量级放入大Ο记号中。
4.2. 常见时间复杂度
时间复杂度越大,算法的执行效率越低,常见的算法时间复杂度由小到大依次为:Ο(1)<Ο(log n)<Ο(n)<Ο(nlog n)<O(n²)<…<Ο(2^n)<Ο(n!)。
常数阶O(1)
下面代码无论执行多少行赋值和加减,只要没有循环等结构,那这个时间复杂度就都是O(1),水平面,如:
var i int
j := 20
z := j + i
g := j - i
线性阶O(n)
从下面可看出,a语句时间频度为1,b语句时间频度为n,c语句频度为n,那么T(n) = 1 + n + n = 2n + 1,根据忽略特点,可得T(n) = n,即时间复杂度为O(n) 。
sun := 0 // a
for i := 0; i < n; i++ { // b
sun = sun + i // c
}
一般来说,只有一个循环结构,输入规模和执行次数都是线性相关的,那么这个代码的时间复杂度就都是O(n) 。
对数阶O(logn)
从下面代码中,语句a时间频度为1,语句b里,在for循环体里,可用公式表示 n = 2^x,x = log2n,T(n) = 1 + log2n,因常数可忽略,因此时间复杂度为O(logn)。
i := 1; // a
for i < n {
i = i * 2 // b
}
线性对数阶O(nlogn)
线性对数阶相当于是上面的对数阶和线性阶的结合,对数阶套了n次循环,相当于 T(n) = n*O(logn),时间复杂度就是O(nlogn)
for 1 := 1; i < n; i++ {
j := 1
for i <= n {
i = i * 2
}
}
平方阶O(n²)
平方阶可简单看作是线性阶中又嵌套了一个线性阶,即O(logn)*O(logn),下面的复杂度就是O(n²)。n次方阶O(n!)的道理同样可这样类推。
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
sun = j + i
}
}
5. 空间复杂度
空间复杂度主要指算法或程序运行所需要的存储空间大小,用于对程序运行过程中所需要的临时存储空间的度量.和时间复杂度类似,空间复杂度通常也使用大O记号来渐进地表示。
5.1. 常见空间复杂度
一般情况,只要算法不涉及到动态分配的空间,以及递归、栈所需的空间,空间复杂度通常为0(1)。一个一维数组,空间复杂度为O(n),二维数组为O(n^2)。
空间复杂度 O(1)
下面代码中临时空间不会随着n的变化而变化,因此空间复杂度为O(1)
i := 1; // a
for i < n {
i = i * 2 // b
}
空间复杂度 O(n)
下面代码中,只有for循环内每次循环赋值一次,因此,对应的空间复杂度为 O(n)。
sun := make([]int)
for i := 0; i < n; i++ {
sun[i] = 2 * i
}
6. 复杂度的四个概念
- 平均时间复杂度:用代码在所有情况下执行的次数的加权平均值表示
- 最好情况时间复杂度:代码在最好情况下执行的时间复杂度。
- 最坏情况时间复杂度:代码在最坏情况下执行的时间复杂度。
- 均摊时间复杂度:在代码执行的所有复杂度情况中绝大部分是低级别的复杂度,个别情况是高级别复杂度且发生具有时序关系时,可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。
例如:
针对排序的几种算法的时间复杂度对比。
排序方法 | 平均时间 | 最好时间 | 最坏时间 | 辅助空间 | 稳定性 | 复杂性 |
---|---|---|---|---|---|---|
冒泡 | O(n²) | O(n) | O(n²) | O(1) | 稳定 | 简单 |
直接选择 | O(n²) | O(n) | O(n²) | O(1) | 不稳定 | 简单 |
直接插入 | O(n²) | O(n) | O(n²) | O(1) | 稳定 | 简单 |
二分插入 | O(n²) | O(n) | O(n²) | O(1) | 稳定 | 简单 |
希尔 | O(n^1.25) | O(1) | 不稳定 | 较复杂 | ||
归并 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | 较复杂 |
快排 | O(nlogn) | O(nlogn) | O(n²) | O(nlogn) | 不稳定 | 较复杂 |
堆 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 不稳定 | 较复杂 |
基数 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(n+r) | 稳定 | 较复杂 |