第29页 | 算法技术手册 | 阅读 ‧ 电子书库

性能指标

比较算法的时候，我们使用输入数据的规模n来评价算法的性能。这个方法被认为是比较算法的标准方法，并且在过去的半个世纪中不断地被改进。这样一来，我们就能够通过输入数据的规模，计算算法的运行时间，从而得知，哪个算法能够更好地适应一些异常规模的问题。性能评价的第二种方法是考虑算法将会耗费多少内存或者存储空间。随后我们将在各自的算法章节中讨论这个问题。

我们将要使用的本书特有的算法分类（按照效率降序排列），如下所示。

·常数级

·对数级

·次线性级

·线性级

·n log(n)级

·平方级

·指数级

我们现在进行一些讨论，陈述一下衡量这些性能的标准。

讨论0：常数级算法的性能

当本书分析算法性能时，我们将不止一次地强调原生的操作都是常数级的性能。很明显，这个声明并不是完全准确地描述了操作的性能，因为我们没有考虑到硬件问题。例如，比较两个32位的数x和y大小是否一样，这个操作耗费的时间与x、y的大小无关。常数的操作被定义为O(1)的性能。

那么比较256位的数字时，性能表现又如何呢？1024位呢？我们认为在给定k的前提下，比较两个k位的数字的操作将在常数时间内完成。关键在于问题的规模（例如x、y的值）不可能超过k。我们把额外的工作，例如k的倍增，也抽象为O(1)的性能。