算法时间复杂度和空间复杂度

源起

作为一个非科班出身的IT从业者，总是有心去研究计算机底层知识相关的技术。内存机制，文件系统，磁盘机制，CPU工作原理等等，是看了又忘，忘了又看，往复循环也算是理解了那么一点点皮毛。leetcode上的算法题目也是刷过那么一点点的，倒是关于算法的复杂度的知识从来都是一掠而过，就在此系统记录一下相关知识。

时间复杂度&空间复杂度定义

时间复杂度

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 n （必须比 n0 大）的输入，它至多需要 5n3 + 3n 的时间运行完毕，那么它的渐近时间复杂度是 O(n3)。

为了计算时间复杂度，我们通常会估计算法的操作单元数量，每个单元运行的时间都是相同的。因此，总运行时间和算法的操作单元数量最多相差一个常量系数。

相同大小的不同输入值仍可能造成算法的运行时间不同，因此我们通常使用算法的最坏情况复杂度，记为 T(n) ，定义为任何大小的输入 n 所需的最大运行时间。另一种较少使用的方法是平均情况复杂度，通常有特别指定才会使用。时间复杂度可以用函数 T(n) 的自然特性加以分类，举例来说，有着 T(n) = O(n) 的算法被称作“线性时间算法”；而 T(n) = O(Mn) 和 Mn= O(T(n)) ，其中 M ≥ n > 1 的算法被称作“指数时间算法”

空间复杂度

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。

定义小节

读完这定义真有删库跑路的冲动了。
精诚所至金石为开，继续学下去吧。

cheetsheet (常见时间复杂度列表)

数据复杂度对照表

以下表格统整了一些常用的时间复杂度类别。表中，poly(x) = xO(1)，也就是 x 的多项式。
数据复杂度对照表

为什么要进行算法分析

预测算法所需的资源

- 计算时间（CPU 消耗）
- 内存空间（RAM 消耗）
- 通信时间（带宽消耗）

预测算法的运行时间

- 在给定输入规模时，所执行的基本操作数量。
- 或者称为算法复杂度（Algorithm Complexity）

复杂度计算实例🌰

常数时间

若算法的T(n) = O(log n)，则称其具有对数时间。由于计算机使用二进制的记数系统，对数常常以2为底（即log2 n，有时写作lg n）。然而，由对数的换底公式，loga n和logb n只有一个常数因子不同，这个因子在大O记法中被丢弃。因此记作O（log n），而不论对数的底是多少，是对数时间算法的标准记法。

常见的具有对数时间的算法有二叉树的相关操作和二分搜索。

稍后更新

如果T(n)=O(c)，其中 c是一个常数，这记法等价于标准记法T(n)=O(1)

对数时间

常见的具有对数时间的算法有二叉树的相关操作和二分搜索。

对数时间的算法是非常有效的，因为每增加一个输入，其所需要的额外计算时间会变小。

递归地将字符串砍半并且输出是这个类别函数的一个简单例子。它需要O（log n）的时间因为每次输出之前我们都将字符串砍半。这意味着，如果我们想增加输出的次数，我们需要将字符串长度加倍。

稍后更新

幂对数时间

这个真是不记得了
对于某个常数k，若算法的T(n) = O((log n)k)，则称其具有幂对数时间。例如，矩阵链排序可以通过一个PRAM模型.[3]被在幂对数时间内解决。

稍后更新

次线性时间

对于一个算法，若其匹配T(n) = o(n)，则其时间复杂度为次线性时间（sub-linear time或sublinear time）。实际上除了匹配以上定义的算法，其他一些算法也拥有次线性时间的时间复杂度。例如有O(n½) 葛罗佛搜索算法。

常见的非合次线性时间算法都采用了诸如平行处理（就像NC1 matrix行列式计算那样）、非古典处理（如同葛罗佛搜索那样），又或者选择性地对有保证的输入结构作出假设（如幂对数时间的二分搜索）。不过，一些情况，例如在头 log(n) 比特中每个字符串有一个比特作为索引的字符串组就可能依赖于输入的每个比特，但又匹配次线性时间的条件。

“次线性时间算法”通常指那些不匹配前一段的描述的算法。它们通常运行于传统电脑架构系列并且不容许任何对输入的事先假设。[4]但是它们可以是随机化算法，而且必须是真随机算法除了特殊情况

线性时间

这个略
如果一个算法的时间复杂度为O(n)，则称这个算法具有线性时间，或O(n)时间。非正式地说，这意味着对于足够大的输入，运行时间增加的大小与输入成线性关系。例如，一个计算列表所有元素的和的程序，需要的时间与列表的长度成正比。这个描述是稍微不准确的，因为运行时间可能显著偏离一个精确的比例，尤其是对于较小的n。

线性对数（准线性）时间

这个略
若一个算法时间复杂度T(n) = O(nlog n)，则称这个算法具有线性对数时间。因此，从其表达式我们也可以看到，线性对数时间增长得比线性时间要快，但是对于任何含有n，且n的幂指数大于1的多项式时间来说，线性对数时间却增长得慢。

源起

时间复杂度&空间复杂度 定义