在解决问题之前，我们可以试着猜测下，在这个问题所依赖的平台（或者平台家族）和数据上，哪个算法将会获得最好的性能。计算一个算法的期望运行时间本质上是一个数学运算过程。在本章，我们将透过现象看本质，阐述隐藏在这些复杂计算内的数学工具以及使用方法。通过本章的阅读，读者应该能够理解本书将要使用的数学术语。
贯穿本章（实际上是贯穿整本书）的一个共同主题就是所有的假设和近似操作都会花费常数时间，但是最终我们得到抽象结论的时候，都会忽略这些常数时间。在所有的平台上，相比影响本书所述的算法性能的其他因素来说，这些常数都是小到可以忽略不计的。
问题样本的规模
问题样本是解决问题的程序所使用的数据集，在大部分问题中，随着已编码样本的规模的增长，程序的执行时间也不断增加。同时，紧凑地对样本数据进行编码（也许使用压缩技术）可能会不必要地降低程序的执行效率。寻找一条最优的样本编码方式是极其困难的，因为问题发生在现实世界，而且机器需要理解这种编码方式。我们需要合理地编码样本数据，以供计算机进行求解。让我们看看接下来边栏“编码的样本”中对数字x的两种表示方法。
我们评价算法时，尽量假设算法是否能够被有效实现不取决于问题样本的编码。在上一个问题中，我们看到，虽然编码方式在规模上差不多，但是在查询奇偶性的这个关键操作上，它们的性能差异非常明显。
选择合适的问题样本编码取决于将会进行的操作。设计一个高效的算法通常是从选择一个合适的数据结构开始的，数据结构通常是在计算机中表示将要解决的问题。如图2-1所示。
图 2-1 问题样本的复杂编码样本编码
给你一个很大的数字x，要求计算x的二进制形式中1的个数的奇偶性（也就是说，1的个数是奇数还是偶数）。例如，如果x=15 137 300 128，其二进制表示是：
x2=1110000110010000001101111010100000
可以看到1的个数是偶数，我们考虑下面两种可行的编码策略：
x的编码1：1110000110010000001101111010100000
x的这个二进制表示方法使用了34个字节。注意到log2(x)的值是33.82，因此这个编码方式是最理想的。但是为了计算1的个数的奇偶性，需要检查每一个位。这种编码方式下，计算奇偶性的最佳时间的增长与x的长度n（x的对数）增长呈线性关系。
x也能够用下面的方式来表示，使用n个位，再加上一个额外的校检位来表示1的数目的奇偶性。
x的编码2：1110000110010000001101111010100000[0]
我们可以看到x的这种编码方式的最后一个位是0，这表示1的个数为偶数个（偶数用0表示）。对于这种表示法，需要35个字节。在两种编码方式中，样本编码的规模都随x的值对数增长。但是，在第一种编码方式中，计算奇偶性最佳算法的时间增长情况与x的编码规模的增长呈对数关系，但是第二种编码方式中，最佳算法只需要花费常数的时间，而且与x编码规模无关。
由于不能够限定问题样本的规模，所以我们假设样本的编码使用一种简洁的方式，可以大致被接受的。当对n个数字进行排序时，我们根据惯例在平台上用一个字来表示数字，这样样本的规模就是n。可能有些数字需要用不止一个字来表示，所以样本的规模也会受到相应的影响。例如，相比使用32位存储整数的类似算法，使用64位来存储整数的算法需要花费两倍时间。
为了存储数据集，大多数编程语言都支持数组，数组是连续的内存区域，这些区域都可以通过一个整数索引i直接快速存取。数组是一维的，每个元素大小用一个字来存储，例如整数数组，布尔数组，或者字符数组，字的大小是平台相关的。有些数组是多维的，这样能够更丰富地表示数据，如图2-1所示，“编码对性能的影响”指出了编码能够影响一个算法的性能。
由于编程语言和平台的巨大差异，算法研究人员认为，即使给定编码方式，计算出精确的性能开销也是不可能的。因此，他们假定，如果一些算法的性能开销仅仅是常数倍差异，那么这些性能开销可以被认为是渐进等价的。但是这个假定在现实世界中是不可行的（谁会愿意将自己的应付账单乘以1000呢？），因此只是在比较算法的时候作为通用的手段。当实现一个算法的时候，对细节的重视反映在关注常数倍差异。