《算法技术手册》一2.4 性能指标

2.4 性能指标

在比较算法时，我们使用了问题数据的规模n来评估算法的性能。这是过去半个世纪算法比较的标准方法。通过输入数据的规模评估算法的执行时间，我们可以知晓哪种算法能够更好地适应一些异常规模的问题。性能评估的第二种方法是考虑算法将会耗费多少内存或者存储空间。之后的小节详细讨论这个问题。
常见的算法分类（按照效率降序排列）如下：
常数级：O(1)
对数级：O(log n)
次线性级：O(nd)，其中d < 1
线性级：O(n)
线性对数级：O(n log n)
平方级: O(n2)
指数级：O(2n)
注意：在评估算法性能时，必须要找到算法中计算费用最大的部分才能决定算法的分类。例如，如果一个算法可以被划分为两个任务，其中一个任务为线性级，另一个任务为平方级，那么这个算法的总体性能应当归为平方级。
下面将通过一些例子来阐释这些不同的性能分类。