基础知识第2讲基础知识

第2讲基础知识1汪信息科学技术学院算法设计与分析2数学基础函数的渐近的界常见函数的阶求和技巧与和的渐进界估计递推方程求解主定理证明及应用3函数的渐近的界下列公式表示的确切含义是什么？f

(n)

=

O(g(n))f

(n)

=

(g(n))f

(n)

=

o(g(n))f

(n)

=

(g(n))f

(n)

=

(g(n))函数的渐近的界定义1.1

设f

和g是定义域为自然数集

N上的函数若存在正数c

和n0，使得对一切n

n0

有0

f(n)

cg(n)成立，则称f(n)的渐近的上界是g(n)，记作f

(n)=O(g(n)).若存在正数c

和n0，使得对一切n

n0

有0

cg(n)

f(n)

成立，则称

f(n)

的渐近的下界是

g(n)，记作f

(n)=(g(n)).函数的渐近的界若对任意正数c

都存在

n0，使得当

n

n0

时有0

f(n)<cg(n)成立,则记作

f(n)=o(g(n)).若对任意正数c

都存在n0，使得当n

n0

时有0

cg(n)<f(n)成立,则记作

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

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

(n)=(g(n)),则记作

f

(n)=(g(n)).例函数f(n)=n2

+n，f(n)

=

O(n2),

f(n)

=

O(n3),

f(n)

=

o(n3),

f(n)

=

(n2)有关定理定理1.1

设

f

和

g

是定义域为自然数集合的函数.(1)如果存在且等于某个常数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)证：根据极限定义，对于给定的正数

=

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))。有关阶的一些性质定理1.2

设

f,

g,

h

是定义域为自然数集合的函数，(1)如果(2)如果(3)如定理果1.3

假设

f和

g

是定义域为自然数集合的函数，若对某个其它的函数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).实例例题设，证明

f(n)=(n2).证：因为2

3n1

n2n2

n2lim

f

(n)

lim

2

1n

n根据定理1.1有f(n)=(n2).可以证明：多项式函数，幂函数的阶低于指数函数nd

=

o(rn)，r

>1，d

>02f

(n)

1

n2

3n对数函数符号：log

n

log2

nlogk

n

(log

n)kloglog

n

log(log

n)性质：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为某个常数例题：函数的阶按照阶从高到低对以下函数排序：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,结果：n22

,

n!,

n2n

,

(3

/

2)n

,取整函数x：表示小于等于x

的最大的整数x：表示大于等于x

的最小的整数取整函数具有下述性质：(1)

x-1<

x

x

x<

x+1

x+n

=x+n,x+n

=x+n，其中n为整数(3)

n

n

n2

ab

n

ba

n

n

b

(4)a

2

n

ab

,递推方程的求解设序列

a0,

a1,

…,

an,

…,

简记为

{an},

一个把

an与某些个ai(i<n)联系起来的等式叫做关于序列{an}的递推方程例子：an

=an-1

+an-2,a0

=0,a1

=1求解目标:

给出

an

的关于

n

的显示公式!

!=15

!

!−

!

!2!=

1

+5

,

!=

1

−

52序列求和几个有用的结果nn(a

a

)akk1

1

n

2k等差级数{a

}naqk

k0a(1

qn1

)1

qnk115k1

ln

n

1等比级数{aqk}调和级数{1/k}序列求和和的上界成立，则ak

namaxnk

1a0kkn

ak

a0rk

0

k

0

a0

rk

01

rak•假设存在常数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递推方程的求解设序列

a0,

a1,

…,an,

…,简记为

{an},

一个把

an与某些个ai(i<n)

联系起来的等式叫做关于序列

{an}

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

情况下时间分析换元迭代：二分归并排序

情况下时间分析差消迭代：快速排序平均情况下的时间分析迭代模型：递归树尝试法：快速排序平均情况下的时间分析主定理：递归算法的分析直接迭代：

排序算法1.4

InsertSort(A,n)

//

A为n个数的数组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二分归并排序//归并排序数组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//将排序数组A[p..q]与A[q+1,r]合并//x,y分别为两个子数组的元素数将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已经是空数组//C已经是空数组

...

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*使用迭代法，对解可以通过数学归纳法验证换元迭代差消化简后迭代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生成过程递归树的应用实例求解：T(n)=T(n/3)+T(2n/3)+nn

nnn99n32n32n2n2n9n9层数

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为常函数，左边=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递推方程的归纳证明•尝试（猜测）递推方程的解应用归纳法严格证明归纳法求解递推方程的三个步骤猜测解的形式用数学归纳法证明找出使解有效的常数确定常数使边界条件成立常用技巧通过引入低阶项获得更紧的解的形式31递推方程的归纳证明例：T(n)=4T(n/2)+n[假定T(1)=Θ(1)]猜测T(n)=Ο(n3)（分别证明Ο和Ω

关系）假设，对于所有的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是某个适当的常数）T(n)

=

Θ(1)于是当1≤n

<n0时，只要c

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

cn3但这个界并不够紧更紧的上界来证明

T(n)

=

Ο

(n2)假设对于所有的

k<n，有

T(k)

≤

ck2T(n)

=

4T(n/2)

+

n≤

4c(n/2)2

+

n

=

cn2

+

n=

Ο

(n2)=

cn2

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

>0，上式最后一步不可能成立！错！必须证明完全一致的形式

期望的形式-余项3435更紧的上界要点：加强归纳假设*减去一个低阶项假设：对于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

当c2

>1可以取c1

足够大来处理初始情况。36例：T(n)=4T(n/2)+n

=Ω(n2)再证明：

T(n)

=Ω(n2)假设对于

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通过改变变量转化递归式，将√n

转化为整数。令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)主定理定理：设a1,

b>1为常数，f(n)为函数，T(n)为非负整数，且T(n)=aT(n/b)+f(n)则有以下结果：若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,且对某个常数c

<1

和所有充分大的n

有a

f(n/b)

c

f(n)，那么

T(n)=

(f(n))主定理的应用例9

求解递推方程T

(n)

9T(n

/

3)

na

9,

b

3,

f

(n)

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

9

n2

,

f

(n)

O(nlog3

91

),相当于主定理的第一种情况，其中=1.根据定理得到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相当于主定理的第二种情况.根据定理得到.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不妨设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

))应用实例，例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成立.相当于主定理的第三种情况.因此有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