2.1 问题样本的规模

问题样本是解决问题的程序所使用的特定输入数据集。在大部分问题中，随着这一数据集规模的增长，程序的执行时间也在不断增加。同时，过度地对样本数据进行编码（可能使用了压缩技术），可能会不必要地降低程序的执行效率。寻找一种最优的样本编码方式是极其困难的，因为问题发生在复杂的现实世界，而且还需要进行合理的翻译才能被程序求解。

在评估算法时，我们会尽量假定问题样本的编码并不是影响算法效率的决定性因素。问题样本的表现方式应当仅仅依赖于待执行操作的类型。设计高效的算法通常从选择一个合适的数据结构开始。由于没法对问题样本给出正式定义，因此我们假设样本以一种简洁且可以普遍接受的方式对样本进行编码。例如，当对n个数字进行排序时，根据惯例，我们会假定数字可以存储在计算平台上32位的字长里，并且待排序的样本规模为n。假如某些数字需要用多于1个字长的空间存储，例如某个固定数量的字长，那么在衡量样本空间时会多乘上一个常量。算法研究人员认为，即使给定编码方式，要精确计算出性能费用也是不切实际的。因此，他们断言，如果一些算法的性能费用仅仅是常数倍的差异，那么它们可以被认为是渐近等价的。换句话说，问题空间的不断增长所带来的算法性能差异是无关紧要的。举例来说，处理64位整数要比处理32位整数需要更长的处理时间，但是这些差异是可以忽略不计的。如果一个优秀的算法能够处理上百万的32位整数，那么它同样可以处理相同数量的64位整数。不过，这个假定在现实世界中是不可行的（谁会愿意将自己应付的账单乘上1000 呢？），因此这种方式只作为算法比较时的一种通用手段。对于本书所涉及的算法，常量对所有平台的影响几乎都是很小的，但在产品代码中具体实现算法时，读者还必须要注意这些常数所带来的影响。这种渐近表示方式之所以非常实用，是因为它可以根据算法在小数据中的性能，来预测其在大数据中的性能。此外，它可以帮助决定特定算法实现能够处理的最大问题样本（Bentley，1999）。大多数编程语言都支持使用数组存储数据集。数组是一块连续的内存区域，这些区域可以通过整数索引i直接和快速地存取第i个元素。当数组元素大小都在1个字长以内时，可以使用一维数组存储（例如整数数组和布尔数组）。当然，数组还可以扩展到多维来表示更为复杂的数据。