算法設(shè)計(jì)與分析第2章數(shù)學(xué)預(yù)備知識(shí)

算法設(shè)計(jì)與分析——數(shù)學(xué)預(yù)備知識(shí)數(shù)學(xué)預(yù)備知識(shí)主要內(nèi)容：介紹算法設(shè)計(jì)與分析中必需的數(shù)學(xué)知識(shí)。

數(shù)學(xué)預(yù)備知識(shí)一.算法分析中相關(guān)的數(shù)學(xué)工具

（2.1~2.7）集合、關(guān)系、函數(shù)、對(duì)數(shù)和證明方法（自行復(fù)習(xí)）2．底函數(shù)和頂函數(shù)(2.4)

設(shè)x為實(shí)數(shù)?！竦缀瘮?shù)：小于或等于x的最大整數(shù)?！耥敽瘮?shù)：大于或等于x的最小整數(shù)。例：=3=-4=4=-3數(shù)學(xué)預(yù)備知識(shí)一.算法分析中相關(guān)的數(shù)學(xué)工具

（2.1~2.7）2．底函數(shù)和頂函數(shù)(2.4P45)●相關(guān)性質(zhì)：

(1)=x,x為整數(shù)

(2)，x為實(shí)數(shù)

(3)定理2.1設(shè)f(x)是單調(diào)遞增連續(xù)函數(shù)，使得若f(x)是整數(shù)，則x是整數(shù)。那么，且●定理2.1的應(yīng)用(P45)數(shù)學(xué)預(yù)備知識(shí)一.算法分析中相關(guān)的數(shù)學(xué)工具

（2.1~2.7）3.階乘和二項(xiàng)式系數(shù)（排列和組合）●Stirling公式：n!●關(guān)于二項(xiàng)式系數(shù)的有關(guān)公式：

●帕斯卡三角形（圖2.1P48）

數(shù)學(xué)預(yù)備知識(shí)一.算法分析中相關(guān)的數(shù)學(xué)工具

（2.1~2.7）4.鴿巢原理(P48)

●定理2.3(鴿巢原理)如果把n個(gè)球分別放在m個(gè)盒子中，那么：

(1)存在一個(gè)盒子，必定至少裝個(gè)球；

(2)存在一個(gè)盒子，必定最多裝個(gè)球；●例2.13(P48)

數(shù)學(xué)預(yù)備知識(shí)一.算法分析中相關(guān)的數(shù)學(xué)工具

（2.1~2.7）5.和式(2.7P48)

●和式的不同表示法：

其中,f(1),f(2),…,f(n)是1,2,…,n的一個(gè)排列。例如，上述公式在簡(jiǎn)化和變換含和式的表達(dá)式時(shí)是很有用的。另外還可變換和式的下標(biāo)（見(jiàn)例2.14）。數(shù)學(xué)預(yù)備知識(shí)一.算法分析中相關(guān)的數(shù)學(xué)工具

（2.1~2.7）5.和式

●常用的級(jí)數(shù)（P49）數(shù)學(xué)預(yù)備知識(shí)一.算法分析中相關(guān)的數(shù)學(xué)工具

（2.1~2.7）6.求和的積分近似可利用積分得到一些和式值的上下界，從而得到和式的近似值。利用定積分的幾何性質(zhì)，可得如下結(jié)論。（見(jiàn)圖2.2,2.3）●若f(x)是單調(diào)遞減的，則若f(x)是單調(diào)遞增的，則

●例2.16數(shù)學(xué)預(yù)備知識(shí)二.遞歸方程（遞推式）的解法

(2.8)

遞歸算法的時(shí)間復(fù)雜性滿足遞歸方程。例1:二分查找算法的最壞情況下時(shí)間復(fù)雜性滿足如下遞歸方程：

(1)

數(shù)學(xué)預(yù)備知識(shí)二.遞歸方程（遞推式）的解法

(2.8)

例2:Hanoi塔問(wèn)題的遞歸算法的時(shí)間復(fù)雜性滿足如下遞歸方程：

(2)

數(shù)學(xué)預(yù)備知識(shí)二.遞歸方程（遞推式）的解法

(2.8)遞推法:利用遞歸關(guān)系反復(fù)遞推展開(kāi)，直至初始值為止。

●例1.遞歸方程(2)●例2.遞歸方程(1)

遞推法適用于解遞歸關(guān)系較簡(jiǎn)單的遞歸方程。數(shù)學(xué)預(yù)備知識(shí)二.遞歸方程（遞推式）的解法

(2.8)2.線性齊次遞歸方程的求解(1)k階線性齊次遞歸方程：（簡(jiǎn)稱齊次方程）

f(n)=a1f(n-1)+a2f(n-2)+…+akf(n-k)(1)

其中，k≤n,ai為常數(shù)，i=1,2,…,n，ak≠0?！颀R次方程的特征方程：

xk-a1xk-1-a2xk-2-…-ak-1x-ak=0●齊次方程的特征根：其特征方程的根。要解k階齊次方程需要k個(gè)初始條件。數(shù)學(xué)預(yù)備知識(shí)二.遞歸方程（遞推式）的解法

(2.8)2.線性齊次遞歸方程的求解(2)齊次方程的通解●設(shè)r為齊次方程(1)的一個(gè)特征根，令f(n)=rn,則

f(n)為齊次方程(1)的一個(gè)特解。

數(shù)學(xué)預(yù)備知識(shí)●齊次方程(1)的通解：設(shè)齊次方程(1)的k個(gè)特征根為r1,r2,…,rk

。若r1,r2,…,rk互不相同，則

f(n)=c1r1n+c2r2n+…+ckrkn

若齊次方程(1)有m個(gè)重特征根ri=ri+1=…=ri+m-1,則f(n)=c1r1n+…+ci-1ri-1n+(ci+ci+1n+…+ci+m-1nm-1)rin+ci+mri+mn+…+ckrkn

其中，c1,c2,…,ck為待定常數(shù)，由齊次方程(1)的k個(gè)初始條件確定。數(shù)學(xué)預(yù)備知識(shí)二.遞歸方程（遞推式）的解法

(2.8)2.線性齊次遞歸方程的求解(3)齊次方程的求解步驟

1）求出齊次方程的所有特征根。

2）構(gòu)造通解的一般形式，系數(shù)待定。

3）將通解代入初始條件，得到一個(gè)關(guān)于系數(shù)的線性方程組。

4）解該線性方程組得所有系數(shù)，代入通解得齊次方程的解。數(shù)學(xué)預(yù)備知識(shí)二.遞歸方程（遞推式）的解法

(2.8)2.線性齊次遞歸方程的求解(4)例子(P53)

例2.18

例2.19

例2.20數(shù)學(xué)預(yù)備知識(shí)二.遞歸方程（遞推式）的解法

(2.8)3.非齊次遞推關(guān)系的求解一般來(lái)說(shuō)沒(méi)有容易的辦法處理非齊次遞推關(guān)系。例2.21例2.22數(shù)學(xué)預(yù)備知識(shí)二.遞歸方程（遞推式）的解法

(2.8)4.一類特殊遞歸方程的求解用分治法解題時(shí)，分治算法的時(shí)間復(fù)雜性常滿足如下形式的遞歸方程：其中，a,c為正整數(shù)，d為非負(fù)常量，g(n)為非負(fù)函數(shù)。數(shù)學(xué)預(yù)備知識(shí)二.遞歸方程（遞推式）的解法

(2.8)4.一類特殊遞歸方程的求解解的一般形式：（設(shè)n=ck）

其中，稱為方程的齊次解，稱為方程的特解。(關(guān)于這個(gè)解的推導(dǎo)可采用更換變?cè)?

數(shù)學(xué)預(yù)備知識(shí)二.遞歸方程（遞推式）的解法

(2.8)4.一類特殊遞歸方程的求解g(n)=bnx(b,x為非負(fù)常量)情況下的解：

其中，n=ck。（引理2.1P57）其中，n為任意正整數(shù)。（定理2.5P58）

訂正定理2.5數(shù)學(xué)預(yù)備知識(shí)二.遞歸方程（遞推式）的解法

(2.8)4.一類特殊遞歸方程的求解g(n)=b(b為非負(fù)常量)情況下的解：(x=0的情況)

其中，n=ck

。其中，n為任意正整數(shù)。

數(shù)學(xué)預(yù)備知識(shí)二.遞歸方程（遞推式）的解法

(2.8)4.一類特殊遞歸方程的求解g(n)=bn(b為非負(fù)常量)情況下的解：(x=1的情況)其中，n=ck

。（推論2.2P58）其中，n為任意正整數(shù)。

數(shù)學(xué)預(yù)備知識(shí)二.遞歸方程（遞推式）的解法

(2.8)4.一類特殊遞歸方程的求解例：求下列遞歸方程的解：設(shè)f(1)=1(1)f(n)=4f(n/2)+n(2)f(n)=4f(n/2)+3n2(3)f(n)=4f(n/2)+n3

數(shù)學(xué)預(yù)備知識(shí)二.遞歸方程（遞推式）的解法

(2.8)4.一類特殊遞歸方程的求解

g(n)為其它函數(shù)情況下的解