2.1 数学运算背后的算法操作
虽然我们已经熟知很多数学概念与性质，但是从算法设计与分析的角度来看，还需要进一步将这些数学的概念与算法的运作联系起来。下面就从这一角度来讨论几组算法设计与分析中常用的数学概念与性质。
2.1.1 取整x和x
我们熟知取整函数的定义：下取整函数x表示不超过x的最大整数；上取整函数x表示不小于x的最小整数。需要取整函数的本质原因在于算法分析中涉及的一些量往往是某种离散对象的个数，它必然是正整数。例如，算法的代价是关键操作的个数，问题的规模经常表示为输入元素的个数、输入数值的比特数等。但是算法分析所需的一些数学函数，其结果却不一定是整数。此时我们经常需要使用取整函数使得结果的表述是准确的。
例如在折半查找中(参见9.1节算法32)，当对数组A［1..n］进行折半时，中点大致在n+12的位置。但是精确来说，折半的位置是数组的某个下标，其必然为整数。所以我们可以借助取整函数，将折半的位置严格表示为n+12或者n+12。再如，在进行合并排序(参见6.2节)的时候，问题的规模不断缩小到原来的12。大致经过log2n次递归，问题规模降低到大小为1的基础情况(base case)。因为递归的次数必然是一个正整数，严格地讲是经过了log2n次递归，问题的规模缩小到1。
2.1.2 对数log n
对数logab的概念大家是熟悉的。需要特别提醒的是，对数符号的使用由于不同领域习惯的不同经常带来一些歧义。在本书中，我们用log n 表示log2n，用lnn表示自然对数logen，用lg n表示常用对数log10n。在算法设计与分析中，至少3类重要的算法操作与对数log n紧密关联，并且通过分析我们发现这3类算法操作之间也有着本质的联系。
●折半：当划分规模为n的问题的时候，大约经过log n次划分，问题规模会降到规模为常数的基础情况。不同的划分方法(如两等分、三等分或者不均匀的某种划分)、不同的基础情况(基础情况的规模可能是1也可能是稍大的某个常数值)，其结果会有细节上的不同，但是具体的值总是log n乘以某个系数。
●二叉树：一个n个节点的完美二叉树(定义见附录B），它的高度为log n。对于更一般的情况，一棵平衡二叉树的高度大致为log n ≌饫锏摹捌胶狻笔且桓霾皇 分精确的概念，进一步的讨论可以参考9.2节平衡二叉搜索树的例子和10.2.2节平衡根树的例子。 ?
平衡二叉树的高度和上面讨论的“折半至基础情况的次数”之间有紧密的联系。为了简化讨论，我们考虑完美二叉树。一个有n个节点的完美二叉树有n+12个叶节点，即大约有一半的节点为叶节点。当去掉树中所有的叶节点时，从高度的角度看，树的高度减少1；从节点数目的角度看，节点数目减少一半。因此完美二叉树的高度与折半至基础情况的次数均为log n。更进一步，如果按层从上到下，每层从左到右将完美二叉树的节点分别标为1,2,3,4…，如图2.1所示，则二叉树的分层可以看作对正整数的一个等价类划分，而log n 是划分的依据：1|2,3|4,5,6,7|8,9,…,15|16…上述的整数划分可以帮助我们得出一些与对数、取整函数相关的更深入的结论(如习题2.2)，而这些结论会在分析相关算法的过程中发挥重要的作用。
●二进制数的比特数：一个十进制的自然数n的二进制表示所需的比特数为log n+1。这跟前面讨论的折半同样有着密切的关联。当我们将一个二进制数右移一位时，从二进制表示的角度看，比特数减1；从数值的角度看，数值变为原来的12。因此整数n二进制表示的比特数，也就大致等于将n折半至基础情况的次数，即log n。
图2.1 完美二叉树节点按层标号
2.1.3 阶乘n!
对于n个不同的元素，其全排列的个数为n!，而对排列的计数在算法设计与分析中有着诸多应用。例如，对于待排序的n个元素，它们输入时的初始顺序是这些元素所有n!种排列中的某一种，而它们排好序后的结果，也是所有排列中的某一种。对于n个不同元素的排序，如果假设所有可能的输入等概率出现，则每种输入出现的概率为1n!。
阶乘是一个连乘形式，如果对它取对数则变成求和形式，而连乘和求和都不易处理。为此，我们可以利用Stirling公式，将阶乘转换成更易于处理的闭形式。具体而言，对于n≥1，有：2πnnen表2.1 Stirling公式的误差
近似 n≥1 n≥10 n≥100 n≥10002πnnen <10%< 1% <0.1%<0.01% 2πnnene112n <1%<0.01 % <0.0001%<0.000001%
2.1.4 常见级数求和∑ni=1f(i)
求和与算法分析的关系非常紧密。算法经常需要反复对输入的元素进行处理，如多轮的循环或者递归，而多轮处理中关键操作的计数往往体现为某种级数的求和。算法的平均情况时间复杂度的定义本身就是级数求和的形式。为此，熟练掌握一些常用数列的求和对算法分析是很有必要的。
●多项式级数(polynomial series)：我们分别给出3组多项式级数，其中一次方的情况是大家熟知的算术级数(arithmetic series)；k次方的情况对于算法设计与分析来说，更有用的是记住其使用Θ记号(详见2.2节的定义)表述的结果。∑ni=1i=n(n+1)2
∑ni=1i2=13nn+12(n+1)
∑ni=1ik=Θ1k+1nk+1
●几何级数(geometric series)：一般形式为：∑ki=0ari=ark+1－1r－1它的两个常用的特例是a=1，r=2或者12的情况：∑ki=012i=2－12k
∑ki=02i=2k+1－1与多项式级数类似的是，在算法分析中我们需要记住几何级数使用Θ记号的形式：∑ki=0ari=Θ(rk)其直观含义是，公比不等于1的几何级数的和(的渐近增长率)就等于最大的那一项，其余项均可以忽略。
●算术几何级数(arithmetic-geometric series)：∑ki=1i・2i=(k－1)2k+1+2
●调和级数（harmonic series）：∑ki=11i=lnk+γ+εk这里γ是欧拉常数；εk是一个小量，它近似为12k，且随着k的增加而趋于0。
●斐波那契数列(Fibonacci numbers)：Fn=Fn－1+Fn－2,n≥2
F0=0,F1=1斐波那契数列的第n项为：Fn=151+52n－1－52n2.1.5 期望E［X］
随机变量及其期望值的概念与算法分析有着本质的关联。算法的平均情况时间复杂度的定义就是一种期望值。正如我们在1.3.3节所定义的，算法的复杂度是一个随机变量，对于不同的输入复杂度是不同的。如果知道算法输入的概率分布，进而计算出算法复杂度的概率分布，则我们可以将算法复杂度的期望值定义为算法的平均情况时间复杂度。
根据对抽象算法分析的讨论，我们知道算法的代价是通过对关键操作的执行进行计数而得出的。如果集中关注单个关键操作的执行情况，则可以为之引入一类特别的随机变量：指标随机变量(indicator random variable)。指标随机变量与某个随机事件e相关联，其定义如下所示。
定义2.1（指标随机变量）Xi=I{事件ei}=1，事件ei发生
0，事件ei未发生很容易验证，指标随机变量的期望值E［Xi］就等于事件ei发生的概率。
指标随机变量在分析算法的平均情况时间复杂度的过程中有广泛的应用。以基于比较的排序算法为例，假设有待排序元素Z={z1,z2,…,zn}。我们定义指标随机变量Xij=I{zi和zj发生了比较｝，则排序的代价可以用指标随机变量表示为：X=∑n－1i=1∑nj=i+1Xij进而排序算法的平均情况时间复杂度可以表示为：E［X］=E∑n－1i=1∑nj=i+1Xij基于指标随机变量的帮助，我们就将分析算法平均情况时间复杂度的问题变成了求一个复杂随机变量的期望值的问题。该期望值的直接求解往往是困难的，但是基于期望值的线性特征(linearity of expectation)，我们可以显著地简化这一问题。
定理2.1 （期望值的线性特征） 给定任意随机变量X1,X2,…,Xk和它们的线性函数h(X1,X2,…,Xk)，我们有：E［h(X1,X2,…,Xk)］=h(E［X1］,E［X2］,…,E［Xk］)需要特别强调的是，这里的任意k个随机变量，无论它们是否独立，上述等式均成立。最常用的多个随机变量的线性函数就是它们的求和，即：E∑ni=1xi=∑ni=1E［xi］基于期望值的线性特征，我们可以进一步推进上述排序算法的分析：E［X］=E∑n－1i=1∑nj=i+1Xij
=∑n－1i=1∑nj=i+1E［Xij］
=∑n－1i=1∑nj=i+1Pr{zi和zj发生了比较}这样，我们就把一个复杂随机变量的期望值的分析分解成了单个(和关键操作紧密相关的)随机事件发生概率的分析。结合具体算法的具体情况，我们可以分析这些关键操作相关的事件发生的概率，再通过级数求和最终得出算法的平均情况时间复杂度。我们将在6.1.3节使用这一方法对快速排序的平均情况时间复杂度进行深入分析。
