本文是王争的算法训练营《第一讲 复杂度分析》的学习笔记，分享了时间复杂度的由来，大 O 时间复杂度表示法，几种常见的时间复杂度量级，最好、最坏、平均时间复杂度，均摊时间复杂度和摊还分析，空间复杂度分析等等
概要
本文是王争的算法训练营《第一讲 复杂度分析》的学习笔记，分享了时间复杂度的由来，大 O 时间复杂度表示法，几种常见的时间复杂度量级，最好、最坏、平均时间复杂度，均摊时间复杂度和摊还分析，空间复杂度分析等等
目录- 时间复杂度的由来
- 大 O 时间复杂度表示法
- 几种常见的时间复杂度量级
- 最好、最坏、平均时间复杂度
- 均摊时间复杂度和摊还分析
- 空间复杂度分析
public int sum(int n){
int result = 0;
for (int i = 1; i <= n; i++){
result = result + i;
}
return result;
}
有一种方法就是在代码的前后加上时间的统计语句
public int sum(int n){
long startTime = System.currentTimeMillis();
int result = 0;
for (int i = 1; i <= n; i++){
result = result + i;
}
long endTime = System.currentTimeMillis();
long costTime = endTime - startTime;
System.out.println("执行代码花费时间为：" + costTime + "ms");
return result;
}
这种方法有两个问题
- 依赖机器、测试数据（或数据规模）等测试环境
- 需要写测试代码，需要真的运行代码测试
- 不依赖机器、测试数据（或数据规模）等测试环境
- 不需要写测试代码，需要真的运行代码测试
- 通过肉眼、读代码、粗略来分析
估算下面一段代码的执行效率
public int sum(int n){
int result = 0; // k1 * unit_time
for (int i = 1; i <= n; i++){ // k2 * unit_time
result = result + i; // k3 * unit_time
}
return result; // // k4 * unit_time
}
- 程序->编译成->机器指令->CPU执行
- 机器指令平均执行时间 unit_time
总执行时间 = k1 * unit_time + n * k2 * unit_time + n * k3 * unit_time + k4 * unit_time
= (k1 + k4) * unit_time + n * (k2 + k3) * unit_time
用代码的执行时间来表示执行效率，还是比较繁琐的，比较不方便拿来沟通的
大 O 时间复杂度表示法 什么是大 O 时间复杂度表示法- 只表示数据规模 n 很大时候的执行效率
- 忽略低阶、常量、系数，只保留最高“量级”
- 表示执行时间随数据规模的增长趋势，而不是具体的执行时间
90 + 6 * n + 7 * n^2 + 8 * n^3 ≈ n^3
大 O 时间复杂度表示法的计算方法public int sum(int n){
int result = 0; // k1 * unit_time 1次
for (int i = 1; i <= n; i++){ // k2 * unit_time n次
result = result + i; // k3 * unit_time n次
}
return result; // // k4 * unit_time 1次
}
总执行时间 = k1 * unit_time + n * k2 * unit_time + n * k3 * unit_time + k4 * unit_time
= (k1 + k4) * unit_time + n * (k2 + k3) * unit_time
O(n) 忽略低阶、常量、系数
时间复杂度分析练习public int f(int n) {
int result = 0; // k1 * unit_time 1次
for (int i = 1; i <= n; i++){ // k2 * unit_time n次
for (int j = 1; j <= n; ++j){ // k3 * unit_time n^2次
result = result + i * j; // k4 * unit_time n^2次
}
}
return result; // // k5 * unit_time 1次
}
总执行时间 = (k1 + k5) * unit_time + n * k2 * unit_time + n^2 * (k3 + k4) * unit_time
O(n^2) 忽略低阶、常量、系数
实际上，时间复杂度跟执行次数最多的那段代码的执行次数成正比
能不能进行一些优化呢？result = (1 * 1 + 1 * 2 + ... + 1 * n) + (2 * 1 + 2 * 2 + ... + 2 * n) + ... + (n * 1 + n * 2 + ... + n * n)
计算过程优化为：
result = 1 * (1 + 2 + ... + n) + 2 * (1 + 2 + ... + n) + ... + n * (1 + 2 + ... + n)
然后抽出同样的 (1 + 2 + ... + n) 为 temp，修改代码如下
public int f2(int n) {
int tmp = 0;
for (int i = 1; i <= n; i++){
tmp = tmp + 1;
}
int result = 0;
for (int i = 1; i <= n; i++){
result = result + i * tmp;
}
return result;
}
两端代码完成同样的功能，代码 A 的时间复杂度是 O(n^2) ，代码 B 的时间复杂度是 O(n）。那么，代码 B 的执行效率比代码 A 高。
时间复杂度的比较仅限于功能相同的代码之间，如果两段代码功能都不同，比较时间复杂度就没有意义了
几种常见的时间复杂度量级- O(1) 常量级 哈希表上的各种操作
- O(logn) 对数级 二分查找、平衡二叉查找树、跳表
- O(n) 线性 数组和链表的遍历、二叉树遍历
- O(nlogn) 快速排序、归并排序、堆排序
- O(n^2) 冒泡、插入、选择排序
- O（2^n）指数级 回溯去穷举算法、比如八皇后问题、斐波那契数列
- O(n!) 比较少见，求全排列，实际上跟 n^n 同阶
// 返回第一个比 n 大并且为 2 的 k 次方的数
public int f4(int n) { // k1 * unit_time 1次
int i = 1; // k2 * unit_time 1次
while (i <= n){ // k3 * unit_time ?次
i = i * 2; // k4 * unit_time ?次
}
return i; // // k5 * unit_time 1次
}
i = 1, 2, 4, 8, ... 2^k = 2^0 、2^1， 2^2， 2^3 ... 2^k
i = 2^k > n 时，while 循环结束
以 2 为底求对数
log2 2^k > log2 n
等于
k > log2 n
k = log2 n O(log2 n)-> 统一为 O(logn)
为什么要把底数省略掉，统一表示为 O(logn) 呢？我们来看下面这个例子
// 返回第一个比 n 大并且为 3 的 k 次方的数
public int f4(int n) { // k1 * unit_time 1次
int i = 1; // k2 * unit_time 1次
while (i <= n){ // k3 * unit_time ?次
i = i * 3; // k4 * unit_time ?次
}
return i; // // k5 * unit_time 1次
}
i = 1, 3, 9, 27, ... 3^k = 3^0 、3^1， 3^2， 3^3 ... 3^k
i = 3^k > n 时，while 循环结束
k = log3 n
O(log3 n) = O(log3 2 * log2 n)
常数可以省略，所以统一为 O(logn)
最好、最坏、平均时间复杂度 分析下面这段代码的时间复杂度public int search(int a[], int n, int target) {
for (int i = 0; i < n; i++) { // ?次
if (a[i] == target) { // ?次
return i; // 1次
}
}
return -1; // 1次
}
第 2、3 行代码有可能执行了 1 次、2 次、3 次 ... n 次
执行效率并不是稳定的，分情况来看，有的时候很快，有的时候很慢
在不同的情况下，执行效率不同，针对这种情况，如何表示代码的执行效率
类比接口的响应时间，我们选取三个不同统计值来表示这段代码的执行效率：
- 最好情况下的时间复杂度 O(1)，类比接口最小响应时间
- 最差情况下的时间复杂度 O(n)，类比接口最大响应时间
- 平均情况下的时间复杂度 (1 + 2 + 3 + ... + n)/n = O(n)，类比接口平均响应时间
public class Demo{
private int n = 10;
private int a[] = new int[n];
private int count = 0;
public void insert(int data){
if (count == n){
int b[] = new int[n * 2];
for (int i = 0; i < n; i++) {
b[i] = a[i];
}
a = b;
n = n * 2;
}
a[count] = data;
count ++ ;
}
}
在我们不停调用 insert 方法的时候，耗时有一定的规律
Demo demo = new Demo();
demo.insert(1); // O(1)
demo.insert(2); // O(1)
// ...
demo.insert(10); // O(1)
demo.insert(11); // O(n) n = 10
demo.insert(12); // O(1)
// ...
demo.insert(20); // O(1)
demo.insert(21); // O(n) n = 20
demo.insert(22); // O(1)
// ...
demo.insert(40); // O(1)
demo.insert(41); // O(n) n = 40
demo.insert(42); // O(1)
// ...
当数据超过数组容量的时候需要申请一个更大的空间，并把原来的数据拷贝到新的数组里面
申请空间不会特别耗时，但是循环拷贝数据比较耗时
我们把耗时比较多的操作，比如插入第 11 个元素的时候，因为需要申请空间，拷贝数据，把它的耗时均摊到耗时比较少的操作上面，均摊到插入第 12 个到第 20 个元素上
经过均摊之后，每个操作的耗时都是 O(1)，所以时间复杂度就是 O(1)
总结一下对某个数据结构进行一组连续的操作，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且，这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块分析，看是否能将耗时多的那次操作的耗时，均摊到其他耗时少的操作上
利用摊还分析法分析得到的平均时间复杂度，我们给它起了一个有区分度的名字：均摊时间复杂度。实际上，均摊时间复杂度就是一种特殊的平均时间复杂度。能够应用摊还分析法分析均摊时间复杂度的代码不多，常见的就是支持动态扩容的一些数据结构
在能够应用均摊时间复杂度分析的场景中，一般均摊（平均）时间复杂度就等于最好时间复杂度
空间复杂度分析// 反转数组
public void reverse(int a[], int n){
int tmp[] = new int[n];
for (int i = 0; i < n; i++) {
tmp[i] = a[n-i-1];
}
for (int i = 0; i < n; i++) {
a[i] = tmp[i];
}
}
空间复杂度 O(n)
// 反转数组
public void reverse2(int a[], int n){
for (int i = 0; i < n/2; i++) {
int tmp = a[i];
a[i] = a[n-i-1];
a[n-i-1] = tmp;
}
}
空间复杂度 O(1)
- 空间复杂度 -> 峰值
- 时间复杂度 -> 累加值
https://github.com/MingsonZheng/algorithm
参考王争的算法训练营(第5期)
https://www.xzgedu.com
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
欢迎转载、使用、重新发布，但务必保留文章署名 郑子铭 （包含链接： http://www.cnblogs.com/MingsonZheng/ ），不得用于商业目的，基于本文修改后的作品务必以相同的许可发布。
如有任何疑问，请与我联系 (MingsonZheng@outlook.com) 。