算法技术手册（原书第2 版）

算法的数学原理

｜

29

算法的

数学原理

其他的加法实现应该会有不同的常数，但是它们的总体表现仍然呈线性。这个结果让那

些认为整数算术是常数操作的程序员大吃一惊。不过，当整数的位数固定（例如

16

位

或者

64

位）时，我们可以认为加法是常数时间。

在考虑算法之间的差异时，了解算法的增长率比常数

c

更为重要。看似无关紧要的差

异可能就会导致不同的性能。加法算法的

plus

实现试图通过消除取模计算（

%

）来提

升算法效率。尽管如此，在

plus

和

add

都

采用

-O3

优化时，

add

还是要比

plus

实现快

30%

。当然，这并不是说可以忽略掉常数

c

的值。如果做大量的

加法

，那么

c

的一点点

小变动都会对程序的性能产生很大的影响。

2.4.5 线性对数算法的性能

性能指标很好地描述了同类算法的共同行为。为了更好地阐述算法在实践中的行为，

我们定义了一个函数

t

(

n

)

，用于表示算法解决样本规模为

n

的问题所需要的时间。分治

法是解决问题的一个高效方法，它将规模为

n

的问题划分成（大致相等的）两个规模为

n/

2

的子问题，并通过递归解决问题。这些子问题会通过线性时间

方式合并在一起来解

决原先规模为

n

的问题。使用数学表达式可以表示为：

t

(

n

) =

2

*

t

(

n/2

) +

c

*

n

也就是说，

t

(

n

)

包括了解决两个子问题和归并结果的

费用，其中归并结果的费用不超过

线性时间（即

c

*

n

）。在等式的右边，

t

(

n

/

2

)

是解决规模为

n/

2

的问题的时间，按此逻辑

推理，

t

(

n

/2)

可以表示为：

t

(

n

/2) = 2

*

t

(

n/

4) +

c

*

n

/2

所以最初的等式可以写为： ...