我们的科学家前辈们发现当我们试图去用执行时间作为独立于具体程序或计算机的度量指标去描述一个算法的时候，确定这个算法所需要的步骤数目非常重要。如果我们把算法程序中的每一步看作是一个基本的计量单位，那么一个算法的执行时间就可以看作是解决一个问题所需要的总步骤数。但是由于算法的执行过程又各不相同，所以这个每一步，即这个基本的计量单位怎么去选择又是一个令人头秃的问题。
「数量级」函数用来描述当规模 n 增加时，T(n) 函数中增长最快的部分，这个数量级函数我们一般用「大 O」表示，记做 O(f(n))。它提供了计算过程中实际步数的近似值，函数 f(n) 是原始函数 T(n) 中主导部分的简化表示。
在
| f(n) | 阶 | 函数名 |
|---|---|---|
| 常数函数 | ||
| 线性函数 | ||
| 二次函数 | ||
| 对数函数 | ||
| 三次函数 | ||
| 指数函数 |
为了确定这些函数哪些在 T(n) 中占主导地位，就要在 n 增大时对它们进行比较，请看下图（图片来自于 Google 图片）：
在上图中，我们可以看到当 n 很小时，函数之间不易区分，很难说谁处于主导地位，但是当 n 增大时，我们就能看到很明显的区别，谁是老大一目了然：
类比于时间复杂度的讨论，一个算法的空间复杂度是指该算法所耗费的存储空间，计算公式计作：S(n) = O(f(n))。其中 n 也为数据的规模，f(n) 在这里指的是 n 所占存储空间的函数。
一般情况下，我们的程序在机器上运行时，刨去需要存储程序本身的输入数据等之外，还需要存储对数据操作的「存储单元」。如果输入数据所占空间和算法无关，只取决于问题本身，那么只需要分析算法在实现过程中所占的「辅助单元」即可。如果所需的辅助单元是个常数，那么空间复杂度就是 O(1)。
空间复杂度其实在这里更多的是说一下这个概念，因为当今硬件的存储量级比较大，一般不会为了稍微减少一点儿空间复杂度而大动干戈，更多的是去想怎么优化算法的时间复杂度。所以我们在日常写代码的时候就衍生出了用「空间换时间」的做法，并且成为常态。
原文：https://www.cnblogs.com/yueluhun/p/12846788.html