算法的时间和空间复杂度

算法（Algorithm）指用来操作数据、解决程序问题的一组方法。对于同一个问题，使用不同的算法，也许最终得到的结果是一样的，但在过程中消耗的资源和时间却会有很大的区别。

主要从算法所占用的「时间」和「空间」两个维度去考量。

时间维度：是指执行当前算法所消耗的时间，我们通常用「时间复杂度」来描述。

空间维度：是指执行当前算法需要占用多少内存空间，我们通常用「空间复杂度」来描述。

算法的效率主要是看它的时间复杂度和空间复杂度情况。然而，有的时候时间和空间却又是鱼和熊掌，不可兼得的，使用者需要根据实际需求取舍。

比如ThreadLocal就是空间换取时间，多线程就是时间换空间，虽然它们不涉及算法，但思想是想通的。

算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的优劣与否。

为了简便，我们一般在计算时间复杂度往往选取最简单的f(n)表示。例如： $O(2n^2+n+1) = O (3n^2+n+3) = O(7n^2+n) = O(n_2)$ ，一般都只用 $O(n_2)$ 表示就可以了。也就是说，两个算法的时间频度不一样，但很有可能拥有相同的时间复杂度。

例如： $T(n)=n^2+3n+4$ 与 $T(n)=4n^2+2n+1$ 它们的频度不同，但时间复杂度相同，都为 $O(n^2)$ 。

常见的算法时间复杂度由小到大依次为： $O(1)<O(log_2(n))<O(n)<O(nlog_2(n))<O(n^2)<O(n^3)<...<O(n!)$ 。

时间复杂度的分类：最坏时间复杂度：输入数据状态最不理想情况下的时间复杂度，也就是算法时间复杂度的上界。若没有特别声明，时间复杂度就是指最坏时间复杂度。平均时间复杂度：在所有可能的输入实例均以等概率出现的情况下，算法的期望时间复杂度。最好时间复杂度：输入数据状态最理想情况下的时间复杂度。

设计算法的时候，我们还会关注空间复杂度，空间复杂度是算法在运行过程中临时占用的存储空间大小的度量, 同样是关于问题规模n的函数。但根本上，算法的时间运行效率才是最重要的。只要算法占用的存储空间不要达到计算机无法接受的程度即可。所以，常常通过牺牲空间复杂度来换取算法更加高效的运行时间效率。

根据算法在运行过程中临时占用存储空间的不同，可以将算法分为两类。

原地算法（in-place algorithm）：只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地”进行的，是节省存储的算法。

非原地算法（not-in-place）：需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元。算法临时占用空间是考虑算法空间复杂度时主要考虑的部分。相比于随着问题输入规模扩大而扩大的非原地算法，原地算法是更加简洁高效的算法（仅考虑空间复杂度时）。

数据结构和算法

相关