基礎(chǔ)知識第2講基礎(chǔ)知識

第2講基礎(chǔ)知識1汪信息科學(xué)技術(shù)學(xué)院算法設(shè)計與分析2數(shù)學(xué)基礎(chǔ)函數(shù)的漸近的界常見函數(shù)的階求和技巧與和的漸進界估計遞推方程求解主定理證明及應(yīng)用3函數(shù)的漸近的界下列公式表示的確切含義是什么？f

(n)

=

O(g(n))f

(n)

=

(g(n))f

(n)

=

o(g(n))f

(n)

=

(g(n))f

(n)

=

(g(n))函數(shù)的漸近的界定義1.1

設(shè)f

和g是定義域為自然數(shù)集

N上的函數(shù)若存在正數(shù)c

和n0，使得對一切n

n0

有0

f(n)

cg(n)成立，則稱f(n)的漸近的上界是g(n)，記作f

(n)=O(g(n)).若存在正數(shù)c

和n0，使得對一切n

n0

有0

cg(n)

f(n)

成立，則稱

f(n)

的漸近的下界是

g(n)，記作f

(n)=(g(n)).函數(shù)的漸近的界若對任意正數(shù)c

都存在

n0，使得當(dāng)

n

n0

時有0

f(n)<cg(n)成立,則記作

f(n)=o(g(n)).若對任意正數(shù)c

都存在n0，使得當(dāng)n

n0

時有0

cg(n)<f(n)成立,則記作

f(n)=(g(n)).若f

(n)=O(g(n))且f

(n)=(g(n)),則記作

f

(n)=(g(n)).例函數(shù)f(n)=n2

+n，f(n)

=

O(n2),

f(n)

=

O(n3),

f(n)

=

o(n3),

f(n)

=

(n2)有關(guān)定理定理1.1

設(shè)

f

和

g

是定義域為自然數(shù)集合的函數(shù).(1)如果存在且等于某個常數(shù)c>0，那么f

(n)

=

(g(n)).(2)

如果，那么

f

(n)=o(g(n)).(3)

如果，那么

f

(n)=(g(n)).g(n)lim

f

(n)n

g(n)lim

f

(n)

0n

g(n)lim

f

(n)

n

證明定理1.1(1)證：根據(jù)極限定義，對于給定的正數(shù)

=

c/2,

存在某個n0，只要

n

n0，就有|

f

(n)

c

|

c

f

(n)

c

g(n)

g(n)

c

f

(n)

3c

2c2

g(n)

2對所有的

n

n0，f(n)

2cg(n)，從而推出

f(n)

=

O(g(n))，對所有的

n

n0，f(n)

(c/2)g(n)，從而推出

f(n)

=

(g(n))，于是

f(n)

=

(g(n))。有關(guān)階的一些性質(zhì)定理1.2

設(shè)

f,

g,

h

是定義域為自然數(shù)集合的函數(shù)，(1)如果(2)如果(3)如定理果1.3

假設(shè)

f和

g

是定義域為自然數(shù)集合的函數(shù)，若對某個其它的函數(shù)h,有f

=O(h)和g

=O(h)，那么

f

+g

=O(h).f

=O(g)且g

=O(h)，那么

f

=(g)且g

=(h)，那么

f

=(g)和g

=(h)，那么f

=

O(h).f

=

(h).f

=

(h).實例例題設(shè)，證明

f(n)=(n2).證：因為2

3n1

n2n2

n2lim

f

(n)

lim

2

1n

n根據(jù)定理1.1有f(n)=(n2).可以證明：多項式函數(shù)，冪函數(shù)的階低于指數(shù)函數(shù)nd

=

o(rn)，r

>1，d

>02f

(n)

1

n2

3n對數(shù)函數(shù)符號：log

n

log2

nlogk

n

(log

n)kloglog

n

log(log

n)性質(zhì)：logbn

o(nα

)

α

0alogb

n

nlogb

alogk

n

Θ(logl

n)階乘n!

2n(

n

)n

(1

Θ(

1

))e

nStirling公式n!

=

o(nn)n!

=

(2n)n

ln

n

n

ln

n

lim

e

n

lim

e

1cnln(

2n(

)n

log

n

n

ln

n

/

ln

2

n

ln

nlog(n!)

=

(nlogn)lim

log(n!)

lim

ln(n!)/

ln

2

lim

ln(n!)nnn（1

(

)))

ln 2n

n

ln

nn

nn上述的c為某個常數(shù)例題：函數(shù)的階按照階從高到低對以下函數(shù)排序：log

n

,2log

n

,nloglog

n

,(log

n)log

n

,log

n,

log(n!)3(3

/

2)n

,n

,

log

log

n,

n

log

n,

n,n1/

log

n

,log2

n,

1,

n!,

n2n

,n22

,n3

, log(n!)

Θ(n

log

n),log2

n,

log

n,

log

n

,n1/

logn

Θ(1)(log

n)log

n

nloglogn

,n

Θ(2log

n

),log

log

n,結(jié)果：n22

,

n!,

n2n

,

(3

/

2)n

,取整函數(shù)x：表示小于等于x

的最大的整數(shù)x：表示大于等于x

的最小的整數(shù)取整函數(shù)具有下述性質(zhì)：(1)

x-1<

x

x

x<

x+1

x+n

=x+n,x+n

=x+n，其中n為整數(shù)(3)

n

n

n2

ab

n

ba

n

n

b

(4)a

2

n

ab

,遞推方程的求解設(shè)序列

a0,

a1,

…,

an,

…,

簡記為

{an},

一個把

an與某些個ai(i<n)聯(lián)系起來的等式叫做關(guān)于序列{an}的遞推方程例子：an

=an-1

+an-2,a0

=0,a1

=1求解目標(biāo):

給出

an

的關(guān)于

n

的顯示公式!

!=15

!

!?

!

!2!=

1

+5

,

!=

1

?

52序列求和幾個有用的結(jié)果nn(a

a

)akk1

1

n

2k等差級數(shù){a

}naqk

k0a(1

qn1

)1

qnk115k1

ln

n

1等比級數(shù){aqk}調(diào)和級數(shù){1/k}序列求和和的上界成立，則ak

namaxnk

1a0kkn

ak

a0rk

0

k

0

a0

rk

01

rak?假設(shè)存在常數(shù)r

<1，使得對一切

k

0，ak

1

r求和實例1k1

k

k

1n11k

1

k1kn1

1

k1

k1k1

k

1n1

1

n1

kk1

k21k17n1

1

n

1

1nkt

2t1t1kt1k

t

2t

2t1

t

2tk

t

2t1t1k1kk

k2

2

1

k

12k

1t1k

t

2t

t

12tt1

t0k

t

2tt1k1

k1

t

2t

2tt0

t0求和實例的上界.例7

估計解：由得nk3kk

13k

1k

13kk

k

1a

k

,aak

1

1

k

1

2ak

3

k

312

11

3(

)3k

1

13k

1nk

13kk

1

23估計和式的漸近的界n估計

k

的漸近的界.11n

ln(n

1)x1k

1

kk

1n1dx1n1

1

1

1

ln

n

1xk

2

knk

1

kndx遞推方程的求解設(shè)序列

a0,

a1,

…,an,

…,簡記為

{an},

一個把

an與某些個ai(i<n)

聯(lián)系起來的等式叫做關(guān)于序列

{an}

的遞推方程求解方法:迭代法直接迭代：排序

情況下時間分析換元迭代：二分歸并排序

情況下時間分析差消迭代：快速排序平均情況下的時間分析迭代模型：遞歸樹嘗試法：快速排序平均情況下的時間分析主定理：遞歸算法的分析直接迭代：

排序算法1.4

InsertSort(A,n)

//

A為n個數(shù)的數(shù)組1.

for

j2

to

n

doxA[j]ij-1

//

行3到行7把A[j]

A[1..j-1]之中while

i>0

and

x<A[i]

doA[i+1]A[i]ii-1A[i+1]xW(1)

0W(n)

W

(n

1)

n

1W(n)

=

W(n-1)+n-1

=

[W(n-2)+n-2]+n-1

=

W(n-2)+(n-2)+(n-1)=

[W(n-3)+n-3]+(n-2)+(n-1)

=

…=

W(1)+1+2+…+(n-2)+(n-1)=

1+2+…+(n-2)+(n-1)=n(n-1)/2二分歸并排序//歸并排序數(shù)組A[p..r]算法1.5

MergeSort(A,

p,

r)if

p<rthen

q(p+r)/23.4.5.MergeSort(A,p,q)MergeSort(A,q+1,r)Merge(A,p,q,r)W

(1)

0W(n)

2W

(n/2)

n

1歸并過程算法1.6

Merge(A,p,q,r)1.

xq-p+1,

yr-q//將排序數(shù)組A[p..q]與A[q+1,r]合并//x,y分別為兩個子數(shù)組的元素數(shù)將A[p..q]

到B[1..x],

將A[q+1..r]

到C[1..y]i1,

j1,

kpwhile

ix

and

jy

do//B的首元素不大于C的首元素//將B的首元素放到A中if

B[i]C[j]then

A[k]B[i]ii+1elseA[k]C[j]jj+1kk+1if

i>x

then

將C[j..y]

到A[k..r]else

將B[i..x]

到A[k..r]//B已經(jīng)是空數(shù)組//C已經(jīng)是空數(shù)組

...

2

1)

1

...

2k

2

(2k

1

2k

W

(1)

k

2k

k

2k

2k

1

n

log

n

n

1W

(n)

2W

(

2k

1

)

2k

1

2[2W

(2k

2

)

2k

1

1]

2k

1

22W

(2k

2

)

2k

2

2k

1

22[2W

(2k

3

)

2k

2

1]

2k

2

2kW

(1)

0W(n)

2W

(n/2)

n

1,

n

2k*使用迭代法，對解可以通過數(shù)學(xué)歸納法驗證換元迭代差消化簡后迭代n1nT

(n)

2T

(i)

cn2i

1n2(n

1)T(n

1)

2T

(i)

c(n

1)2i

1nT

(n)

(n

1)T(n

1)

2cn

cT

(n)

T

(n

1)

2cn

c

13

2n1

1

...

1

T

(1)]

O( )

Θ(log

n)n

1

nn

1

n n(n

1)

2c[快速排序平均時間分析2

n1n

i1

T(n)

T(i)

cn,

n

2

T(1)

0T

(n)

Θ(nlog

n)迭代模型：遞歸樹441

1

n

2kW(1)

0n

4n

1n

1n

1n

1n

2n2

1n2

1n

1n

14

4W(n)n-‐1W(n/2)W(n/2)n-‐1n/2-1

n/2-1W(n/4)W(n/4)

W(n/4)

W(n/4)1

1

1

1

11W(n)

2W(

n/2

)

n

1,

n

2k

,W

(n)

n

1

n

2

...

n

2k

kn

(2k

1)

nlog

n

n

1生成過程遞歸樹的應(yīng)用實例求解：T(n)=T(n/3)+T(2n/3)+nn

nnn99n32n32n2n2n9n9層數(shù)

k:

(1)

O(n)n(2/3)k

=Θ(1)

(3/2)k=Θ(n)

k=O(log3/2n)T(n)=O(nlogn)嘗試法：快速排序T

(n)

T

(i)

O(n)2

n1n

i

1(1)T(n)=C為常函數(shù)，左邊=O(1)右邊=2

C(n

1)

O(n)

2C

2C

O(n)n

n(2)T(n)=cn,左邊=cn2n2

n

2c

(1

n

1)(n

1)1ci

O(n)

O(n)

cn

c

O(n)n

i

1右邊=322

2cn

3n

O(n)

O(n

)]

O(n)(3)T(n)=cn2,左邊=cn22

n1

ci

2右邊=

O(n)

2

[

cn3n

i

1(4)T(n)=cnlogn,左邊=cnlognni

log

i

O(n)

cnlog

n

O(n)2cn1i

1右邊以積分作為求和的近似4

4

ln

2

4

ln

2

2ln

2

222

2n2

ln

n

1

41

n2ln

2

24

1

x2

ln

x

x2

x

x

log

xdx

ln

2

ln

xdxnn

nn1i

1n1

n1

2

x

log

xdx

i

log

i

x

log

xdx30遞推方程的歸納證明?嘗試（猜測）遞推方程的解應(yīng)用歸納法嚴(yán)格證明歸納法求解遞推方程的三個步驟猜測解的形式用數(shù)學(xué)歸納法證明找出使解有效的常數(shù)確定常數(shù)使邊界條件成立常用技巧通過引入低階項獲得更緊的解的形式31遞推方程的歸納證明例：T(n)=4T(n/2)+n[假定T(1)=Θ(1)]猜測T(n)=Ο(n3)（分別證明Ο和Ω

關(guān)系）假設(shè)，對于所有的k<nT(k)

≤

ck3通過歸納法證明T(n)

≤

cn3例：T(n)=4T(n/2)+nT(n)

=

4T(n/2)

+

n≤

4c(n/2)3

+

n=

(c/2)n3

+

n=

cn3

–

((c/2)n3

–

n)≤cn3這里要保證：((c/2)n3

–n)≥0，這只需要：c

≥2并且n

≥1于是有T(n)=Ο(n3)余項

期望的形式期望的形式-余項3233例：T(n)=4T(n/2)+n還必須處理初始情形，才能使歸納成立。注意到，因為對所有的1≤n

<n0

都有（其中n0是某個適當(dāng)?shù)某?shù)）T(n)

=

Θ(1)于是當(dāng)1≤n

<n0時，只要c

足夠大，就有“Θ(1)” ≤

cn3但這個界并不夠緊更緊的上界來證明

T(n)

=

Ο

(n2)假設(shè)對于所有的

k<n，有

T(k)

≤

ck2T(n)

=

4T(n/2)

+

n≤

4c(n/2)2

+

n

=

cn2

+

n=

Ο

(n2)=

cn2

–(-n)≤cn2但對任何c

>0，上式最后一步不可能成立！錯！必須證明完全一致的形式

期望的形式-余項3435更緊的上界要點：加強歸納假設(shè)*減去一個低階項假設(shè)：對于k

<n，有T(k)≤c1k2

–c2kT(n)

=

4T(n/2)

+

n≤

4(c1(n/2)2

–

c2(n/2))

+

n=

c1n2

–

2c2n

+

n=

c1n2

–

c2n

–

(c2n

–

n)≤c1n2

–c2n

當(dāng)c2

>1可以取c1

足夠大來處理初始情況。36例：T(n)=4T(n/2)+n

=Ω(n2)再證明：

T(n)

=Ω(n2)假設(shè)對于

k

<

n，有

T(k)

≥ck2T(n)

=

4T(n/2)

+

n≥

4c(n/2)2

+

n=

cn2

+

n取c

足夠小來處理初始情況。T(n)=O(n2)且T(n)=Ω(n2)得T(n)=Θ(n2)37換元法的求解遞推方程例：T(n)=2T(√n)+logn通過改變變量轉(zhuǎn)化遞歸式，將√n

轉(zhuǎn)化為整數(shù)。令m

=logn，于是T(2m)

=

2T(2m/2)

+

m再令S(m)=T(2m)，于是

S(m)=2S(m/2)+m=Θ(mlogm)T(n)

=

T(2m)

=

S(m)

=

Θ(mlogm)=

Θ(logn

loglogn)主定理定理：設(shè)a1,

b>1為常數(shù)，f(n)為函數(shù)，T(n)為非負(fù)整數(shù)，且T(n)=aT(n/b)+f(n)則有以下結(jié)果：若f

(n)

O(nlog

b

a

),

0,

那么T

(n)

Θ(nlogb

a

)若f

(n)

Θ(nlog

b

a

),

那么T

(n)

Θ(nlogb

a

log

n)若f

(n)

Ω(nlog

b

a

),

0,且對某個常數(shù)c

<1

和所有充分大的n

有a

f(n/b)

c

f(n)，那么

T(n)=

(f(n))主定理的應(yīng)用例9

求解遞推方程T

(n)

9T(n

/

3)

na

9,

b

3,

f

(n)

n,解 上述遞推方程中的那么nlog3

9

n2

,

f

(n)

O(nlog3

91

),相當(dāng)于主定理的第一種情況，其中=1.根據(jù)定理得到T

(n)

Θ(n2

)例10

求解遞推方程

T(n)

T

(2n

/

3)

1解

上述遞推方程中的

a=1,

b=3/2,

f(n)=1，那么nlog3/2

1

n0

1,

f

(n)

1相當(dāng)于主定理的第二種情況.根據(jù)定理得到.T(n)

Θ(n0

log

n)

Θ(log

n)f

(n)T(

n

)bT(

n

)bT(

n

)ba40…f

(n)nbf

(

)nbf

(

)nbf

(

)a…b2

b2

b2

b2

b2

b2ab2

b2

b2T(

n

)

T(

n

)

T(

n

)T(

n

)

T(

n

)

T(

n

)T(

n

)

T(

n

)

T(

n

)a41a……

…nbf

(

)nbf

(

)nbf

(

)f

(n)a…aaaaaaaa

a………………………ab2

b2

b2

b2

b2

b2ab2

b2

b2f

(

n

)

f

(

n

)

f

(

n)

f

(

n)

f

(

n

)

f

(

n

)

f

(

n

)

f

(

n

)

f

(

n

)a……

…..................(1)

(1).........(1)

(1)

(1)

(1)

(1)

(1)

(1)

(1)...…logbnf

(n)af

(

n

)bb2a2

f

(n

)...nlogb

a(nlogb

a

)logb

aTotal

(n

)

inbia f

(

)(logb

n

)1i0主定理的證明)bna f

(bna f

(b2

b2b

a[aT

(

n

)

f

(

n

)]

f

(n)

a2T

(

n

)

af

(

n

)

f

(n)jjjjklogb

a)

T

(1)

c1

c1n

a

T

(1)

b

akT

(

n

)

ak

1

f

(

n

)

...

af

(

n

)

f

(n)

...b

bT

(n)

aT

(

n

)

f

(n)k

1j

0k

1j

0bk

bk

1不妨設(shè)n=bk情況1f

(n)

O(nlogb

a

))jlog

ab

jnbk

1j0

a f

(T(n)

c1n)log

a)j

0log

ablogb

n1b

c1nb

jn

O(

a

j

()111

1

1b

c

nj

0(b

)

j

)j

0logb

n1a

a

j(blogb

a

)

jlog

ablogb

n

c

nlogb

a

O(n

logb

a

)logb

n1c

nlogb

a

O(nlogb

a

O(nlogbb1

c

nlogb

a

O(nlogb

a

n

)

Θ(nlogb

a

)情況2f

(n)

Θ(nlogb

a

))jlog

ab

jnbk

1j

0

a f

(T

(n)

c1n)

c1n

blog

an

a

j)bjlogb

alogb

a

c1n

Θ(a

(

)blog

a

Θ(nlogb

a

log

n)1

c

nlogb

n1jj

0logb

n1

a

j

Θ(n

logb

aj

0

Θ(nlogb

a

log

n)情況3f

(

n

)

Ω

(

n

l

o

g

b

a

)

c1n

b

Θ(

f

(n))log

a

Θ(

f

(n))11

1

c

nlog

b

a

c

nlog

b

aj

0log

alogb

n1bc

1clogbn

c

j

f

(n)j

0

f

(n)bn(af

(

)

cf

(n))b

jk

1

a

j

f

(

n

)1T

(n)

c

n（c

1）(

f

(n)

Ω(nlogb

a

))應(yīng)用實例，例11

求解遞推方程T

(n)

3T(n

/

4)

n

log

n解

上述遞推方程中的a=3,

b=4,

f(n)=nlogn，那么n

log

n

Ω(nlog4

3

)

Ω(n0.793

)0.2此外，要使af(n/b)

cf(n)成立，代入f(n)=nlogn，得到4

43n

log

n

cn

log

n顯然只要

c

3/4，上述不等式就可以對充分大的n成立.相當(dāng)于主定理的第三種情況.因此有T(n)

Θ(

f

(n))

Θ(nlogn)不能直接使用主定理的例子例12

求解T

(n)

2T

(n

/

2)

n

log

na=b=2,

nlog2

2

n，

f(n)=nlogn不存在

>

0

使得

nlogn

=(n1+)

成立，nlognn(log

n

1)2n(log

n

1)2n(log

n

2)4n(log

n

2)4n(log

n

2)4n(log

n

2)4………nlognn(logn-1)n(logn-2)T(n)

nlog

n