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

[toc]

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

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

4.1 常用算法复杂度趋势

O(log n), O(1) O(n) O(n log n) O(n^2) O(2^n) O(n!) 算法操作元素

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

更多相关专栏内容汇总：

Java 核心知识-专栏文章目录汇总

Java 并发编程-专栏文章目录汇总

Java JVM（JDK13）-专栏文章目录汇总

数据结构与算法-专栏文章目录汇总

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

时间复杂度与空间复杂度.md

时间复杂度与空间复杂度.md

1.算法

2.时间复杂度

2.1 时间频度

2.2 时间复杂度的定义

2.2.1 忽略项

2.2.2 计算时间复杂度的方法

2.2.3 常见的时间复杂度

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

3.空间复杂度

4.算法复杂度指南

4.1 常用算法复杂度趋势

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

4.3 排序算法-算法复杂度

参考

Files

时间复杂度与空间复杂度.md

Latest commit

History

时间复杂度与空间复杂度.md

File metadata and controls

1.算法

2.时间复杂度

2.1 时间频度

2.2 时间复杂度的定义

2.2.1 忽略项

2.2.2 计算时间复杂度的方法

2.2.3 常见的时间复杂度

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

3.空间复杂度

4.算法复杂度指南

4.1 常用算法复杂度趋势

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

4.3 排序算法-算法复杂度

参考