《算法導論（原書第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)。