首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》第2章 算法的数学原理

关灯直达底部

在解决问题之前,我们可以试着猜测下,在这个问题所依赖的平台(或者平台家族)和数据上,哪个算法将会获得最好的性能。计算一个算法的期望运行时间本质上是一个数学运算过程。在本章,我们将透过现象看本质,阐述隐藏在这些复杂计算内的数学工具以及使用方法。通过本章的阅读,读者应该能够理解本书将要使用的数学术语。

贯穿本章(实际上是贯穿整本书)的一个共同主题就是所有的假设和近似操作都会花费常数时间,但是最终我们得到抽象结论的时候,都会忽略这些常数时间。在所有的平台上,相比影响本书所述的算法性能的其他因素来说,这些常数都是小到可以忽略不计的。

问题样本的规模

问题样本是解决问题的程序所使用的数据集,在大部分问题中,随着已编码样本的规模的增长,程序的执行时间也不断增加。同时,紧凑地对样本数据进行编码(也许使用压缩技术)可能会不必要地降低程序的执行效率。寻找一条最优的样本编码方式是极其困难的,因为问题发生在现实世界,而且机器需要理解这种编码方式。我们需要合理地编码样本数据,以供计算机进行求解。让我们看看接下来边栏“编码的样本”中对数字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呢?),因此只是在比较算法的时候作为通用的手段。当实现一个算法的时候,对细节的重视反映在关注常数倍差异。