衡量不同算法之间的优劣主要是从算法所占用的「时间」、「空间」两个维度考量，即：
- 时间维度：指执行当前算法所消耗的时间，由流程决定，通常用「时间复杂度」描述。
- 空间维度：指执行当前算法需要占用多少内存空间，由流程决定，通常用「空间复杂度」描述。
时间复杂度
时间复杂度通过运行程序验证所消耗时间时，受运行环境、数据规模等因素影响差异很大，因此使用通用表示法描述时间复杂度。例如，大O符号表示法，即T(n) = O(f(n))，表示代码执行时间随数据规模增长的变化趋势，也叫作渐进时间复杂度（asymptotic time complexity）。
常见时间复杂度量级：
- 常数阶O(1)
- 线性阶O(n)
- 对数阶O(logn)、线性对数阶O(nlogn)
- 平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)
- 指数阶O(2^n)
- 阶乘阶O(n!)
1 | O(1) < O(logn) < O(√n) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!) |
常数时间操作
常数时间操作与算法流程无关，而与实现细节有关，通常不需要参与时间复杂度评估。
常见的常数时间操作有：
- 算术运算，+、-、*、/、%等
- 位运算，>>、>>>、<<、|、&、^等
- 赋值、比较、自增、自减操作
- 数组寻址操作
空间复杂度
空间复杂度全称是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。空间复杂度是对算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。常用的有：O(1)、O(n)、O(n^2)。