
算法的数学原理
|
15
算法的
数学原理
处理
64
位整数要比处理
32
位整数需要更长的处理时间,但是这些差异是可以忽略不计
的。如果一个优秀的算法能够处理上百万的
32
位整数,那么它同样可以处理相同数量的
64
位整数。不过,这个假定在现实世界中是不可行的(谁会愿意将自己应付的账单乘上
1000
呢?),因此这种方式只作为算法比较时的一种通用手段。
对于本书所涉及的算法,常量对所有平台的影响几乎都是很小的,但在产品代码中具体
实现算法时,读者还必须要注意这些常数所带来的影响。这种渐近表示方式之所以非常
实用,是因为它可以根据算法在小数据中的性能,来预测其在大数据中的性能。此外,
它可以帮助决定特定算法实现能够处理的最大问题样本(
Bentley
,
1999
)。
大多数编程语言都支持使用数组存储数据集。数组是一块连续的内存区域,这些区域可
以通过整数索引
i
直接和快速地存取第
i
个元素。当数组元素大小都在
1
个字长以内时,
可以使用一维数组存储(例如整数数组和布尔数组)。当然,数组还可以扩展到多维来
表示更为复杂的数据。
2.2 函数的增长率
我们将算法
执行时间的增长率
描述为一个与输入问题样本规模相关的函数。使用这种方
法描述算法性能会比较抽象,因为它忽略了大量的细节问题。所以,在使用这种方法时,
需要对抽象背后的细节有一个清醒的认识。程序都必须运行在某个平台上,在这里,广
义的平台定义包括:
•
运行程序的计算机,包括
CPU
、数据缓存、浮点运算单元(
FPU
)以及其他芯片特性。
•
程序编写所使用的编程语言、编译器
/
解释器以及用于生成代码的优化设置。 ...