《Hello 算法》第二章 · 算法复杂度

当我们提到算法复杂度时，可以把它当作衡量完成一项任务效率的标准。想象你和朋友一起比赛，看谁能更快地完成整理书架的任务。你们有两种不同的做法，最终谁更快完成任务，谁就是胜利者。通过算法复杂度，我们能够评估不同方法在完成任务时的效率，帮助我们在各种情况下选择最佳的方案。

时间复杂度：任务做得有多快？

时间复杂度就像是完成任务所需要的时间。假设你有100本书要整理，每次拿一本书，你都需要检查它放对了没，直到所有书都摆放好了。那么，整理书架的时间就跟书的数量成正比。

在计算机科学中，算法的时间复杂度通过大O符号表示，用来描述算法的运行时间随输入值大小的变化趋势。它通常忽略低阶项和系数，只关注输入规模趋近无穷时的表现。时间复杂度常用来衡量算法在最坏情况下的执行时间，也可用来分析平均情况。通过估算算法操作单元的数量来计算时间复杂度，常见的分类包括线性时间算法（O(n)）和指数时间算法（O(Mn)）。（总结自Wikipedia）

常见的时间复杂度

O(1) — 常数时间复杂度
如果不管有多少本书，任务所需时间都一样（比如，找几本书），这就是常数时间复杂度。就像你每次做的动作都很简单，任务的大小对时间没有太大影响。
O(n) — 线性时间复杂度
假设你是一本一本地整理书，每增加一本书，整理的时间就多一点。这就是线性时间复杂度，任务量增加，所需时间也按比例增加。
O(n²) — 平方时间复杂度
如果你需要比别人做得更复杂，比如检查每本书与其他每本书的位置是否匹配，时间就会随着任务数量的增加加速增加。每本书要和其他所有书比对一次，这就是平方时间复杂度。
O(log n) — 对数时间复杂度
这种复杂度表示每次操作都会将问题规模缩小一半，导致时间增长相对较慢。比如，二分查找就是这种算法类型，每次将搜索范围减半，大大提升了效率。
O(n log n) — 对数线性时间复杂度
这种复杂度常见于高效的排序算法，比如快速排序和归并排序。它的时间复杂度优于O(n²)，但没有O(n)那样直接。

空间复杂度：做任务需要多少空间？

空间复杂度就像是你整理书架时需要的额外空间。假设你有一张大桌子用来暂时放书，那么空间复杂度就是你需要多少桌子来摆放这些书。

在计算机科学中，空间复杂度描述了一个算法或程序执行时所需的存储空间大小，通常以输入值长度为函数。类似于时间复杂度，空间复杂度也使用大O符号表示，如 O(n)、O(n log n)、O(2^n) 等，其中n代表输入长度，影响算法的空间需求。空间复杂度计算时不考虑算法的执行时间。（总结自Wikipedia）

常见的空间复杂度

O(1) — 常数空间复杂度
如果你只需要一个小桌子就能完成任务，不管书有多少，空间需求都一样。这就是常数空间复杂度，表示你对空间的需求是固定的，不会随任务大小变化。
O(n) — 线性空间复杂度
如果你需要一张桌子来放每一本书，那么空间复杂度就是线性的。随着书的增多，你需要的空间也会增加。

生活中的例子：

O(1)：找固定的物品（比如桌子上的一支笔），不管桌子多大，时间都差不多。
O(n)：检查书包里的所有物品，时间随着物品数量的增加而增加。
O(n²)：如果你需要检查每两件物品之间的匹配情况，随着物品数量增加，任务变得更加复杂。

大O符号

在算法分析中，我们使用大O符号来描述算法的时间或空间复杂度，特别是在最坏情况下。它帮助我们理解数据量增大时，算法性能会如何变化。通过大O符号，我们可以评估不同算法在处理大数据时的效率。

大O符号（Big-O notation）是用来描述算法时间复杂度或空间复杂度的数学符号，表示随着输入数据规模增大，算法的性能或资源需求的增长趋势。大O符号关注的是输入规模趋近无穷时算法的增长速率，忽略常数因子和低阶项，旨在提供算法在最坏情况下的表现。常见的时间复杂度有O(1)（常数时间）、O(n)（线性时间）、O(n²)（平方时间）等，它们帮助我们评估不同算法的效率和适应性，尤其在处理大数据时。（来源：ChatGPT）