这篇文章介绍一下算法基础中关于时间复杂度和空间复杂度的基本内容。

算法衡量指标

衡量算法的两个重要指标：时间复杂度与空间复杂度。

时间复杂度

定义

为了解决对于时间复杂度的分析和衡量，官方提出了时间复杂度的概念：

Asymptotic time complexity（渐进时间复杂度）：若存在函数f(n)，使得当n趋于无穷大时，T(n)/f(n)的极限值为不等于0的常数，则称f(n)是T(n)的同数量级函数，记住T(n)=O(f(n)),称为O(f(n)), O为算法的渐进时间复杂度，简称为时间复杂度。

注：由于时间复杂度使用O来表示，因此也被称为O表示法。

基本原则和表示方法

时间复杂度的推导满足如下几个基本原则，实际了解数学中极限相关的一些基础知识的话，内容非常容易理解。

• 常数量级的时间用常数1表示，时间复杂度记住O(1)
• 函数中只保留最高阶项，比如T(n)=n(n+1)，时间复杂度T(n)=O(n*n)
• 时间复杂度的表示中，省略最高项阶的系数，比如T(n)=2n + 1, 时间复杂度T(n)=O(n)

常见的时间复杂度

• 常数阶 O(1)
• 对数阶 O(log2n)
• 线性阶 O(n)
• 线性对数阶 O(nlog2n)
• 平方阶 O(n^2)
• 立方阶 O(n^3)
• k 次方阶 O(n^k)
• 指数阶 O(2^n)

时间复杂度的比较

在满足n足够大的前提下，上述常见的算法时间复杂度由小到大依次为：Ο(1)＜ Ο(log2n)＜ Ο(n)＜ Ο(nlog2n)＜ Ο(n2)＜ Ο(n3)＜ Ο(nk) ＜ Ο(2n) ，随着问题规模 n 的不断增大，时间复杂度不断增大，算法的执行效率越低，参看下图可以了解到，应该尽可能避免使用指数阶的算法。

空间复杂度

定义

为了解决对于空间复杂度的分析和衡量，空间复杂度的概念如下：

Space complexity（空间复杂度）：若存在f(n)表示所占存储空间的函数，使得当n趋于无穷大时，S(n)/f(n)的极限值为不等于0的常数，则称f(n)是S(n)的同数量级函数，记住S(n)=O(f(n)),称为O(f(n)), O称为算法的空间复杂度。

常见的空间复杂度

• 常数阶 O(1) ： 常量空间，用于算法使用的存储空间大小固定，和输入规模没有直接关系的场景
• 线性阶 O(n)：线性空间，用于算法使用的存储空间是线性集合（比如列表）的情况，线性集合的大小和输入规模n成正比。另外，一般的递归操作相关的空间复杂度也大多跟递归深度n之间的复杂度为线性阶O(n)
• 平方阶 O(n^2)：而为空间，用于算法使用的存储空间是而为列表集合的情况，二维列表的两个纬度的大小都与输入规模n成正比。

策略

在资源有限的情况之下，没有办法两者同时满足，在运算速度和空间资源之间的平衡就是所谓的策略，一般有时间换空间，或者空间换时间的策略。

时间换空间

在考虑运存储空间有限的情况下，以时间换取保存空间的策略称为时间换空间。

空间换时间

在考虑运行时间有限的情况下，以空间换取执行时间的提升的策略称为空间换时间，比如很多缓存类产品，这些能够提升执行的速度。