复盘笔记

专栏原创出处：github-源笔记文件 (opens new window) ，github-源码 (opens new window)，欢迎 Star，转载请附上原文出处链接和本声明。

1.算法
2.时间复杂度
3.空间复杂度
4.算法复杂度指南
参考

# 1.算法

算法是解决特定问题求解步骤的描述，在计算机中表现为指定的有限序列，并且每条指令表示一个或多个操作。

如何衡量算法好坏呢？主要从算法占用的「时间」「空间」两个维度去衡量。

时间：执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。
空间：执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。

有时候鱼和熊掌不可兼得，我们只能尽量寻找一个平衡点。

为了缩短时间，我们可以用空间换时间，加强硬件来让程序更快。或者说我们不在乎时间，我们可以采用廉价的硬件让程序慢慢运行，只要有结果就可以。

# 2.时间复杂度

度量算法执行时间的两种方法：

事后统计的方法：编写算法程序后再进行分析
事前估算的方法：通过分析算法的时间复杂度来判断算法的优劣

# 2.1 时间频度

一个算法中的语句执行次数称为语句频度或时间频度，记为 $T(n)$ 。算法花费的时间与算法中语句的执行次数成正比例，算法中语句执行次数多，它花费时间越长。

例如计算 1 到 n 的和：

// 方式 1：使用 for 循环，一共执行了 2n+2 次
int total = 0;                 // 执行 1 次
for (int i = 1; i <= n; i++) { // 执行 n+1 次
    total += i;                // 执行 n 次
}

// 方式 2：公式直接计算，一共执行了 2 次
int total = 0;            // 执行 1 次
total = (1 + n) * n / 2;  // 执行 1 次
}

因此方式 2 的时间频度更小。

# 2.2 时间复杂度的定义

若有某个辅助函数 $f(n)$ ，使得当 $n$ 趋近于无穷大时， $T(n)/f(n)$ 的极限值为不等于零的常数，则称 $f(n)$ 是 $T(n)$ 的同数量级函数。记作 $T(n) = O(f(n))$ ，称 $O(f(n))$ 为算法的渐进时间复杂度，简称「时间复杂度」。

为什么不用时间频次表示时间复杂度呢？

因为大 O 符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势。随着 n 不断增大，时间频次计算的部分内容可以忽略不计。

我们脑补一下，[ $3n+10$ ] 与 [ $n$ ] 这 2 个表达式在 [n = ∞] 时，两条函数曲线无限接近了。
为了简化时间复杂度的描述，我们直接用 $O(n)$ 描述就可以了。什么乘法系数，常数项都可以忽略不计了。

# 2.2.1 忽略项

对于 $T(n)$ 来说，随着 $n$ 的增大，常数项、低次项、系数可以忽略不计，忽略不计的结果最终描述为时间复杂度。

$T(n)=3n+10$ 与 $T_1(n)=3n$ 随着 $n$ 增大，两条函数曲线无限接近，常数项 10 可忽略。

$T(n)=2n^2+3n+10$ 和 $T_1(n)=2n^2$ 随着 $n$ 增大，两条函数曲线无限接近，低次项 $3n+10$ 可忽略。

$T(n)=5n^2+7n$ 和 $T_1(n)=3n^2 + 2n$ 随着 $n$ 增大，两条函数曲线无限接近， $T(n)$ 系数 5 与 $T_1(n)$ 系数 3 可忽略。

# 2.2.2 计算时间复杂度的方法

假如我们有一个时间频次计算表达式为 $T(n)=3n^2+7n+6$ ，计算步骤如下：

用常数 1 代替运行时间中的所有加法常数为： $3n^2+7n+1$
修改后的运行次数函数中，只保留最高阶项为： $3n^2$
去除最高阶项的系数为： $n^2$

最终得出的时间复杂度为 $O(n^2)$

# 2.2.3 常见的时间复杂度

算法复杂度由小到大依次为：

常数阶 $O(1)$
对数阶 $O(\log_2n)$
线性阶 $O(n)$
线性对数阶 $O(n\log_2n)$
平方阶 $O(n^2)$
立方阶 $O(n^3)$
k 次方阶 $O(n^k)$
指数阶 $O(2^n)$

下面通过一些代码实例来说明常见的复杂度：

常数阶 $O(1)$

无论代码执行多少行，只要没有循环结构等复杂结构，则该段代码的时间复杂度就是 $O(1)$ 。

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

解释说明：上述代码在执行的时候，消耗的时间并不随某个变量的增长而增长，即无论该类代码有多少行，都可以用 $O(1)$ 表示其时间复杂度。

线性阶 $O(n)$

for (i = 1; i <= n; ++i) {
    j = i;
    j++;
}

解释说明：for 循环中的代码会执行 $n$ 遍，因此它消耗的时间是随着 $n$ 的变化而变化的，因此该类代码的时间复杂度用 $O(n)$ 标识。

说明：我们一般看到 $O(n)$ 的复杂度算法，不一定是一个循环，可能是 2 个循环完成的， $O(2n)$ 忽略系数后最终为 $O(n)$ 。

对数阶 $O(\log_2n)$

int i = 1;
while (i < n) {
    i = i * 2;
}

解释说明：在 while 循环中，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近。

假设循环 x 次之后，i 就大于 2 了，此时循环退出，即 2 的 x 次方等于 n，则 $x=\log_2n$ 。

因此该代码的复杂度为 $O(\log_2n)$ 。 $O(\log_2n)$ 中的底数 2 是根据代码变化的，若i = i * 3，则是 $O(\log_3n)$ 。

对数阶 $O(n\log_2n)$

for (i = 1; i <= n; ++i) {
    i = 1;
    while (i < n) {
        i = i * 2;
    }
}

解释说明：将时间复杂度为 $O(\log_2n)$ 的代码循环 $n$ 遍，其时间复杂度即变为 $n*O(\log_2n)$ ，即 $O(n\log_2n)$ 。

平方阶 $O(n^2)$

for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
        a = i + j;
    }
}

解释说明：将时间复杂度为 $O(n)$ 的代码再嵌套循环一遍，时间复杂度则变为 $O(n^2)$ 。

# 2.3 平均时间复杂度和最坏时间复杂度

所有可能的输入实例均以等概率出现的情况下，该算法的运行时间，称为平均时间复杂度。
最坏情况下的时间复杂度称最坏时间复杂度。

一般讨论的时间复杂度均是最坏情况下的时间复杂度。最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上限，保证了算法的运行时间不会比最坏情况更长。

平均时间复杂度和最坏时间复杂度是否一致与具体的算法有关。

# 3.空间复杂度

算法所耗费的存储空间称为空间复杂度。

算法所占用的空间有哪些？

算法本身占用的空间，输入、输出、指令、常数、变量等
算法要使用的辅助空间

空间复杂度特点：

对一个算法在运行过程中临时占用存储空间大小的量度。
空间复杂度是关于 $n$ 的函数，随着 $n$ 的增大，占用的存储越大。

# 4.算法复杂度指南

以下图表来源于 Big-O Cheat Sheet (opens new window)

图例： 极坏的 坏的 一般性 好的 优异的

# 4.1 常用算法复杂度趋势

# 4.2 常用数据结构算法复杂度

数据结构	时间复杂度								空间复杂度
	平均				最差				最差
	访问	查询	插入	删除	访问	查询	插入	删除
数组	`Θ(1)`	`Θ(n)`	`Θ(n)`	`Θ(n)`	`O(1)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
堆	`Θ(n)`	`Θ(n)`	`Θ(1)`	`Θ(1)`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
栈	`Θ(n)`	`Θ(n)`	`Θ(1)`	`Θ(1)`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
单向链表	`Θ(n)`	`Θ(n)`	`Θ(1)`	`Θ(1)`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
双向链表	`Θ(n)`	`Θ(n)`	`Θ(1)`	`Θ(1)`	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
跳跃表	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`O(n)`	`O(n)`	`O(n)`	`O(n)`	`O(n log(n))`
哈希表	`N/A`	`Θ(1)`	`Θ(1)`	`Θ(1)`	`N/A`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
二叉搜索树	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`O(n)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
笛卡尔树	`N/A`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`N/A`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
B 树	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`
红黑树	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`
伸展树	`N/A`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`N/A`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`
AVL Tree	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(log(n))`	`O(n)`
KD Tree	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`Θ(log(n))`	`O(n)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`

# 4.3 排序算法-算法复杂度

排序算法	时间复杂度			空间复杂度
	最好	平均	最差	最差
快排	`Ω(n log(n))`	`Θ(n log(n))`	`O(n^2)`	`O(log(n))`
归并排序	`Ω(n log(n))`	`Θ(n log(n))`	`O(n log(n))`	`O(n)`
Timsort	`Ω(n)`	`Θ(n log(n))`	`O(n log(n))`	`O(n)`
堆排序	`Ω(n log(n))`	`Θ(n log(n))`	`O(n log(n))`	`O(1)`
冒泡排序	`Ω(n)`	`Θ(n^2)`	`O(n^2)`	`O(1)`
插入排序	`Ω(n)`	`Θ(n^2)`	`O(n^2)`	`O(1)`
选择排序	`Ω(n^2)`	`Θ(n^2)`	`O(n^2)`	`O(1)`
Tree Sort	`Ω(n log(n))`	`Θ(n log(n))`	`O(n^2)`	`O(n)`
希尔排序	`Ω(n log(n))`	`Θ(n(log(n))^2)`	`O(n(log(n))^2)`	`O(1)`
桶排序	`Ω(n+k)`	`Θ(n+k)`	`O(n^2)`	`O(n)`
基数排序	`Ω(nk)`	`Θ(nk)`	`O(nk)`	`O(n+k)`
计数排序	`Ω(n+k)`	`Θ(n+k)`	`O(n+k)`	`O(k)`
Cubesort	`Ω(n)`	`Θ(n log(n))`	`O(n log(n))`	`O(n)`

# 参考

《Java 数据结构与算法》韩顺平
Big-O Cheat Sheet (opens new window)

更多相关专栏内容汇总：

Java 核心知识-专栏文章目录汇总 (opens new window)

Java 并发编程-专栏文章目录汇总 (opens new window)

Java JVM（JDK13）-专栏文章目录汇总 (opens new window)

数据结构与算法-专栏文章目录汇总 (opens new window)

← 数据结构概述字符串和数组 →