孙成敏《计算机算法设计与分析》算法分析作业-第二章（给学生）

计算机算法：设计与分析主讲：欧阳继红

ouyangjihong@2011年3月*1本课程的目的12/18/20192介绍经典的算法设计策略；学习如何用经典的算法设计策略设计你自己的算法；教你分析算法效率的方法；引入算法正确性证明方法。讲

义

余祥宣，崔国华，邹海明:计算机算法基础（第三版）,华中科技大学出版社.12/18/20193共11章12/18/20194第1章数学预备知识（自学）第2章，对算法的基本概念以及算法的复杂度、算法的描述工具进行了简要的阐述。第3章——

第9章

设计算法时的一些基本设计策略

。第3章讲一部分，第7章不讲。第10章：NP难度，NP完全问题参考书12/18/20195

王晓东，计算机算法设计与分析，电子工业出版社，2001，1.

Thomas

H.Cormen,Charles

E.Leiserson,el

al.Introduction

to

Algorithms,

MIT

Press,2001,1180

pages.

算法导论（第二版影印版），高等教育出版社，2002.

M.H.Alsuwaiyel,Algorithms

Design

Techniqueand

Analysis,World

Scientific

Publishing

Co.Ltd.,1999.算法设计技巧与分析（英文版），电子工业出版社,2003.

陈慧南，算法设计与分析——C++

语言描述，电子工业出版社，2006.本课把算法的学习内容分成五个不同的方面分析设计算法表示算法确认算法分析算法测试程序12/18/20196分析算法分为两个阶段：12/18/20197事前分析：求出算法的一个时间限界函数。事后测试：收集此算法的执行时间和实际占用空间的统计资料。要确定执行语句的时间总量，需要知道两项基本信息：语句的频率计数P；(即语句的执行次数，与具体机器无关）；每一次执行这条语句所需要的时间。(与具体机器、程序设计语言以及编译程序有关）*8事前分析仅能确定每条语句的频率计数P频率计数已经能够反映出算法的好坏：例：赋值语句

在程序段(a)中的频率计数为(b)

FOR

i=1

TO

n

DO中的频率计数为12/18/20199(C)

forforto

n

doto

n

dorepeatrepeat

中的频率计数为一条语句的数量级：执行此语句的频率一个算法的数量级：执行算法所有语句频率的总和。12/18/201910数量级能衡量算法的好坏例.若解同一问题的三个算法，数量级分别为：n,n2和n3

.取n=10,则n2=100，n3

=1000确定算法的数量级是十分必要的，它在本质上反映了算法所需要的计算时间。12/18/201911计算时间的渐进表示12/18/201912算法的计算时间f(n)：定义2.1

如果存在两个正的常数c12/18/201913和n0，对于所有的，有：则记作：f(n)=O(g(n)).对于非负的f(n)和g(n),可以改为：对定义2.1的说明：12/18/201914当n充分大时，f（n）有上界，g（n）为f（n）的一个上界；f（n）的阶不高于g（n）的阶；f（n）的数量级是g（n）；试图求出满足定义2.1的最小g（n）；有关证明中找c和n0是关键。例：12/18/2019151.证明：3n=O(n)证明：对所有的n≥1，有3n≤4n,设

f(n)=3n

,

取c=4,

根据定义2.1有：f(n)≤cn

，即3n=O(n).2.

n2=O(n3)1.

3.

2n2+11n-10=O(n2)对于非负的f（n）和g（n），根据定义2.1，可以证明O具有如下性质：12/18/201916O(f(n))+O(g(n))

=

O(max(f(n),

g(n))

;O(f(n))+O(g(n))

=

O(f(n)+g(n))

；O(f(n))

O(g(n))

=

O(f(n)

g(n))

；4．如果g(n)=O(f(n))，则O(f(n))+O(g(n))

=

O(f(n))

；O(cf(n))=O(f(n))，其中c是一个正的常数f(n)

=

O(f(n))从计算时间上，将算法分为两类：12/18/201917多项式时间算法：可用多项式来对其计算时间限界的算法例：最常见的6种多项式时间算法：O(1)

<

O(logn)

<

O(n)

<

O(nlogn)

<

O(n2)

<

O(n指数时间算法：可用指数函数来对其计算时间限界的算法例：最常见的指数时间算法：O(2n)

<

O(n！)

<

O(nn)上界函数O,下界函数12/18/201918定义2.2

如果存在两个正的常数c和n0对于所有的

，有：则记作：

f(n)

=

(g(n)).对于非负的f(n)

，可以改为：对定义2.2的说明：12/18/201919当n充分大时，f（n）有下界，g（n）为f（n）的一个下界；f（n）的阶不低于g（n）的阶；试图求出满足定义2.2的最大g（n）；有关证明中找常数c和n0是关键。对于非负的f（n）和g（n），根据定12/18/201920数义2.2，可以证明具有如下性质：(f(n))+

(g(n))

=

(min(f(n),

g(n))

;(f(n))+

(g(n))

=

(f(n)+g(n))

；(f(n))

(g(n))

=

(f(n)

g(n))

；4．如果g(n)

=

(f(n))

，则(f(n))+

(g(n))

=

(f(n))

；

??(cf(n))=

(f(n))，其中c是一个正的常f(n)

=

(f(n))

??若f(n)既是g(n)的上界函数:12/18/201921又是g(n)的下界函数:定义2.3

如果存在正的常数c1,c2和n0，对于所有的

，有：则记作：f(n)=(g(n)),即f(n)与g(n)同作业112/18/2019221.证明:n2=O(n3);证明:2n2+11n-10=O(n2);证明：O的性质3，5;证明：作业112/18/2019235.如果g(n)=(f(n))+(f(n))，则(g(n))

=

(f(n))

；

?(cf(n))=

(f(n))，其中c是一个正的常f(n)

=(f(n))+(f(n))+(f(n))+(f(n))

?(g(n))

=(g(n))

=(g(n))

=(min(f(n),

g(n))

?(max(f(n),

g(n))

?(f(n)+g(n))

?若成立，证明之；不成立，举反例。数学归纳法数学归纳法有多种形式：1.i

=1,结论成立若i

=n-1时成立1.

证明i

=n时结论成立（初始归纳）（归纳假设）（归纳证明）2.2.i

=1,结论成立（初始归纳）（归纳假i

=2,结论成立若i

=n-1,i

=n时结论成立设）5.

证明i

=n+1时结论成立明）12/18/2019（归纳证24数学归纳法12/18/2019253.证明一个特性对所有正整数n成立特性对于1成立，（初始归纳）如果对于所有的n

≥1时，特性对n成立，（归纳假设）证明：特性对n+1成立（归纳证明）2.

用数学归纳法证明：当n

1时，12/18/201926()1

结论成立。2.证明：n

=1时,

log1

=

0假设对所有的

n

1时，成立，证明成立。因为即12/18/201927作业112/18/20192811.用数学归纳法证明：当n≥1时，12.用数学归纳法证明：2012年3月23日（周五）交第一次作业本章小结12/18/201929前言

算法分析的介绍，本课程的地位算法设计与分析是计算机专业中面向设计的、处于核心地位的且十分重要的专业基础课。本课程的目的经典的算法设计策略；用经典的算法设计策略设计算法；分析算法效率的方法；算法正确性证