《算法导论（原书第3版）》一3.2 标准记号与常用函数

本节将回顾一些标准的数学函数与记号并探索它们之间的关系，还将阐明渐近记号的应用。

单调性

若m≤n蕴涵f(m)≤f(n)，则函数f(n)是单调递增的。类似地，若m≤n蕴涵f(m)≥f(n)，则函数f(n)是单调递减的。若mf(n)，则函数f(n)是严格递减的。

53

向下取整与向上取整

对任意实数x，我们用x表示小于或等于x的最大整数(读作“x的向下取整”)，并用x表示大于或等于x的最小整数(读作“x的向上取整”)。对所有实数x，

x-1

对任意整数n，

n/2+n/2=n

对任意实数x≥0和整数a，b>0，

x/ab=xab(3.4)

x/ab=xab(3.5)

ab≤a+（b-1）b(3.6)

ab≥a-（b-1）b(3.7)

向下取整函数f(x)=x是单调递增的，向上取整函数f(x)=x也是单调递增的。

模运算

对任意整数a和任意正整数n，amodn的值就是商a/n的余数：

amodn=a-na/n(3.8)

结果有

0≤amodn

给定一个整数除以另一个整数的余数的良定义后，可以方便地引入表示余数相等的特殊记号。若(amodn)=(bmodn)，则记a≡b(modn)，并称模n时a等价于b。换句话说，若a与b除以n时具有相同的余数，则a≡b(modn)。等价地，a≡b(modn)当且仅当n是b-a的一个因子。若模n时a不等价于b，则记ab(modn)。

54

多项式

给定一个非负整数d，n的d次多项式为具有以下形式的一个函数p(n)：

p(n)=∑di=0aini

其中常量a0，a1，…，ad是多项式的系数且ad≠0。一个多项式为渐近正的当且仅当ad>0。对于一个d次渐近正的多项式p(n)，有p(n)=Θ（nd)。对任意实常量a≥0，函数na单调递增，对任意实常量a≤0，函数na单调递减。若对某个常量k，有f(n)=o(nk)，则称函数f(n)是多项式有界的。

指数

对所有实数a>0、m和n，我们有以下恒等式：

a0=1

a1=a

a-1=1/a

(am)n=amn

(am)n=(an)m

aman=am+n

对所有n和a≥1，函数an关于n单调递增。方便时，我们假定00=1。

可以通过以下事实使多项式与指数的增长率互相关联。对所有使得a>1的实常量a和b，有

limn→∞nban=0(3.10)

据此可得

nb=o(an)

因此，任意底大于1的指数函数比任意多项式函数增长得快。

使用e来表示自然对数函数的底2.71828…，对所有实数x，我们有

55ex=1+x+x22!+x33!+…=∑∞i=0xii!(3.11)

其中“！”表示本节后面定义的阶乘函数。对所有实数x，我们有不等式

ex≥1+x(3.12)

其中只有当x=0时等号才成立。当x≤1时，我们有近似估计

1+x≤ex≤1+x+x2(3.13)

当x→0时，用1+x作为ex的近似是相当好的：

ex=1+x+Θ（x2）

(在这个等式中，渐近记号用来描述当x→0而不是x→∞时的极限行为)。对所有x，我们有：

limn→∞1+xnn=ex(3.14)

对数

我们将使用下面的记号：

lgn=log2n　　(以2为底的对数)

lnn=logen　　(自然对数)

lgkn=（lgn)k　(取幂)

lglgn=lg（lgn)　(复合)

我们将采用的一个重要记号约定是对数函数只适用于公式中的下一项，所以lgn+k意指（lgn)+k而不是lg(n+k)。如果常量b>1，那么对n>0，函数logbn是严格递增的。

对所有实数a>0，b>0，c>0和n，有

a=blogba

logc（ab）=logca+logcb

logban=nlogba

logba=logcalogcb(3.15)

logb(1/a）=-logba

logba=1logab

alogbc=clogba(3.16)

其中，在上面的每个等式中，对数的底不为1。

56

根据等式(3.15)，对数的底从一个常量到另一个常量的更换仅使对数的值改变一个常量因子，所以当我们不关心这些常量因子时，例如在o记号中，我们经常使用记号“lgn”。计算机科学家发现2是对数的最自然的底，因为非常多的算法和数据结构涉及把一个问题分解成两个部分。

当x＜1时，ln(1+x)存在一种简单的级数展开：

ln（1+x)=x-x22+x33-x44+x55-…

对x>-1，还有下面的不等式：

x1+x≤ln（1+x)≤x(3.17)

其中仅对x=0等号成立。

若对某个常量k，f(n)=o（lgkn)，则称函数f(n)是多对数有界的。在等式(3.10)中，通过用lgn代替n并用2a代替a，可以使多项式与多对数的增长互相关联：

limn→∞lgbn（2a）lgn=limn→∞lgbnna=0

根据这个极限，我们可以得到：对任意常量a>0，

lgbn=o（na）

因此，任意正的多项式函数都比任意多对数函数增长得快。

阶乘

记号n!(读作“n的阶乘”)定义为对整数n≥0，有

n!=1若n=0

n·（n-1）!若n＞0

因此，n!=1·2·3…n。

阶乘函数的一个弱上界是n!≤nn，因为在阶乘中，n项的每项最多为n。斯特林（stirling）近似公式

57n!=2πnnen1+Θ1n(3.18)

给出了一个更紧确的上界和下界，其中e是自然对数的底。正如练习3.2-3要求证明的，

n!=o(nn)

n!=ω(2n)

lg(n!)=Θ（nlgn)(3.19)

其中斯特林近似公式有助于证明等式(3.19)。对所有n≥1，下面的等式也成立：

n!=2πnneneαn(3.20)

其中

112n+1＜αn＜112n(3.21)

多重函数

我们使用记号f(i)(n)来表示函数f(n)重复i次作用于一个初值n上。形式化地，假设f(n)为实数集上的一个函数。对非负整数i，我们递归地定义

f（i）（n)=n若i=0

f(f（i-1）（n））若i＞0

例如，若f(n)=2n，则f(i)(n)=2in。

多重对数函数

我们使用记号lg*n（读作“log星n”）来表示多重对数，下面会给出它的定义。假设lg(i)n定义如上，其中f(n)=lgn。因为非正数的对数无定义，所以只有在lg(i-1)n>0时lg(i)n才有定义。一定要区分lg(i)n(从参数n开始，连续应用对数函数i次)与lgin(n的对数的i次幂)。于是定义多重对数函数为

lg*n=min{i≥0:lg(i)n≤1}

多重对数是一个增长非常慢的函数：

lg*2=1

lg*4=2

lg*16=3

lg*65536=4

lg*(265536)=5

58

因为在可探测的宇宙中原子的数目估计约为1080，远远小于265536，所以我们很少遇到一个使lg*n>5的输入规模n。

斐波那契数

使用下面的递归式来定义斐波那契数：

f0=0

f1=1(3.22)

fi=fi-1+fi-2，　i≥2

因此，每个斐波那契数都是两个前面的数之和，产生的序列为

0，1，1，2，3，5，8，13，21，34，55，…

斐波那契数与黄金分割率及其共轭数有关，它们是下列方程的两个根：

x2=x+1(3.23)

并由下面的公式给出（参见练习3.2-6）：

=1+52=1.61803…(3.24)

=1-52=-0.61803…

特别地，我们有

fi=i-i5

可以使用归纳法来证明这个结论（练习3.2-7）。因为<1，所以有

i5＜15＜12

这蕴涵着

59

fi=i5+12(3.25)

这就是说第i个斐波那契数fi等于i/5舍入到最近的整数。因此，斐波那契数以指数形式增长。

练习

3.2-1　证明：若f(n)和g(n)是单调递增的函数，则函数f(n)+g(n)和f(g(n))也是单调递增的，此外，若f(n)和g(n)是非负的，则f(n)·g(n)是单调递增的。

3.2-2　证明等式(3.16)。

3.2-3　证明等式(3.19)。并证明n!=ω(2n)且n!=o(nn)。

*3.2-4　函数lgn!多项式有界吗？函数lglgn!多项式有界吗？

3.2-5　如下两个函数中，哪一个渐近更大些：lg(lgn)还是lg*（lgn)？

3.2-6　证明：黄金分割率及其共轭数都满足方程x2=x+1。

3.2-7　用归纳法证明：第i个斐波那契数满足等式

其中是黄金分割率且是其共轭数。

603.2-8　证明：klnk=Θ（n)蕴涵着k=Θ（n/lnn)。