孫成敏《計(jì)算機(jī)算法設(shè)計(jì)與分析》算法分析作業(yè)-第二章（給學(xué)生）

計(jì)算機(jī)算法：設(shè)計(jì)與分析主講：歐陽繼紅

ouyangjihong@2011年3月*1本課程的目的12/18/20192介紹經(jīng)典的算法設(shè)計(jì)策略；學(xué)習(xí)如何用經(jīng)典的算法設(shè)計(jì)策略設(shè)計(jì)你自己的算法；教你分析算法效率的方法；引入算法正確性證明方法。講

義

余祥宣，崔國(guó)華，鄒海明:計(jì)算機(jī)算法基礎(chǔ)（第三版）,華中科技大學(xué)出版社.12/18/20193共11章12/18/20194第1章數(shù)學(xué)預(yù)備知識(shí)（自學(xué)）第2章，對(duì)算法的基本概念以及算法的復(fù)雜度、算法的描述工具進(jìn)行了簡(jiǎn)要的闡述。第3章——

第9章

設(shè)計(jì)算法時(shí)的一些基本設(shè)計(jì)策略

。第3章講一部分，第7章不講。第10章：NP難度，NP完全問題參考書12/18/20195

王曉東，計(jì)算機(jī)算法設(shè)計(jì)與分析，電子工業(yè)出版社，2001，1.

Thomas

H.Cormen,Charles

E.Leiserson,el

al.Introduction

to

Algorithms,

MIT

Press,2001,1180

pages.

算法導(dǎo)論（第二版影印版），高等教育出版社，2002.

M.H.Alsuwaiyel,Algorithms

Design

Techniqueand

Analysis,World

Scientific

Publishing

Co.Ltd.,1999.算法設(shè)計(jì)技巧與分析（英文版），電子工業(yè)出版社,2003.

陳慧南，算法設(shè)計(jì)與分析——C++

語言描述，電子工業(yè)出版社，2006.本課把算法的學(xué)習(xí)內(nèi)容分成五個(gè)不同的方面分析設(shè)計(jì)算法表示算法確認(rèn)算法分析算法測(cè)試程序12/18/20196分析算法分為兩個(gè)階段：12/18/20197事前分析：求出算法的一個(gè)時(shí)間限界函數(shù)。事后測(cè)試：收集此算法的執(zhí)行時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)資料。要確定執(zhí)行語句的時(shí)間總量，需要知道兩項(xiàng)基本信息：語句的頻率計(jì)數(shù)P；(即語句的執(zhí)行次數(shù)，與具體機(jī)器無關(guān)）；每一次執(zhí)行這條語句所需要的時(shí)間。(與具體機(jī)器、程序設(shè)計(jì)語言以及編譯程序有關(guān)）*8事前分析僅能確定每條語句的頻率計(jì)數(shù)P頻率計(jì)數(shù)已經(jīng)能夠反映出算法的好壞：例：賦值語句

在程序段(a)中的頻率計(jì)數(shù)為(b)

FOR

i=1

TO

n

DO中的頻率計(jì)數(shù)為12/18/20199(C)

forforto

n

doto

n

dorepeatrepeat

中的頻率計(jì)數(shù)為一條語句的數(shù)量級(jí)：執(zhí)行此語句的頻率一個(gè)算法的數(shù)量級(jí)：執(zhí)行算法所有語句頻率的總和。12/18/201910數(shù)量級(jí)能衡量算法的好壞例.若解同一問題的三個(gè)算法，數(shù)量級(jí)分別為：n,n2和n3

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

=1000確定算法的數(shù)量級(jí)是十分必要的，它在本質(zhì)上反映了算法所需要的計(jì)算時(shí)間。12/18/201911計(jì)算時(shí)間的漸進(jìn)表示12/18/201912算法的計(jì)算時(shí)間f(n)：定義2.1

如果存在兩個(gè)正的常數(shù)c12/18/201913和n0，對(duì)于所有的，有：則記作：f(n)=O(g(n)).對(duì)于非負(fù)的f(n)和g(n),可以改為：對(duì)定義2.1的說明：12/18/201914當(dāng)n充分大時(shí)，f（n）有上界，g（n）為f（n）的一個(gè)上界；f（n）的階不高于g（n）的階；f（n）的數(shù)量級(jí)是g（n）；試圖求出滿足定義2.1的最小g（n）；有關(guān)證明中找c和n0是關(guān)鍵。例：12/18/2019151.證明：3n=O(n)證明：對(duì)所有的n≥1，有3n≤4n,設(shè)

f(n)=3n

,

取c=4,

根據(jù)定義2.1有：f(n)≤cn

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

n2=O(n3)1.

3.

2n2+11n-10=O(n2)對(duì)于非負(fù)的f（n）和g（n），根據(jù)定義2.1，可以證明O具有如下性質(zhì)：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是一個(gè)正的常數(shù)f(n)

=

O(f(n))從計(jì)算時(shí)間上，將算法分為兩類：12/18/201917多項(xiàng)式時(shí)間算法：可用多項(xiàng)式來對(duì)其計(jì)算時(shí)間限界的算法例：最常見的6種多項(xiàng)式時(shí)間算法：O(1)

<

O(logn)

<

O(n)

<

O(nlogn)

<

O(n2)

<

O(n指數(shù)時(shí)間算法：可用指數(shù)函數(shù)來對(duì)其計(jì)算時(shí)間限界的算法例：最常見的指數(shù)時(shí)間算法：O(2n)

<

O(n！)

<

O(nn)上界函數(shù)O,下界函數(shù)12/18/201918定義2.2

如果存在兩個(gè)正的常數(shù)c和n0對(duì)于所有的

，有：則記作：

f(n)

=

(g(n)).對(duì)于非負(fù)的f(n)

，可以改為：對(duì)定義2.2的說明：12/18/201919當(dāng)n充分大時(shí)，f（n）有下界，g（n）為f（n）的一個(gè)下界；f（n）的階不低于g（n）的階；試圖求出滿足定義2.2的最大g（n）；有關(guān)證明中找常數(shù)c和n0是關(guān)鍵。對(duì)于非負(fù)的f（n）和g（n），根據(jù)定12/18/201920數(shù)義2.2，可以證明具有如下性質(zhì)：(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是一個(gè)正的常f(n)

=

(f(n))

??若f(n)既是g(n)的上界函數(shù):12/18/201921又是g(n)的下界函數(shù):定義2.3

如果存在正的常數(shù)c1,c2和n0，對(duì)于所有的

，有：則記作：f(n)=(g(n)),即f(n)與g(n)同作業(yè)112/18/2019221.證明:n2=O(n3);證明:2n2+11n-10=O(n2);證明：O的性質(zhì)3，5;證明：作業(yè)112/18/2019235.如果g(n)=(f(n))+(f(n))，則(g(n))

=

(f(n))

；

?(cf(n))=

(f(n))，其中c是一個(gè)正的常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))

?若成立，證明之；不成立，舉反例。數(shù)學(xué)歸納法數(shù)學(xué)歸納法有多種形式：1.i

=1,結(jié)論成立若i

=n-1時(shí)成立1.

證明i

=n時(shí)結(jié)論成立（初始?xì)w納）（歸納假設(shè)）（歸納證明）2.2.i

=1,結(jié)論成立（初始?xì)w納）（歸納假i

=2,結(jié)論成立若i

=n-1,i

=n時(shí)結(jié)論成立設(shè)）5.

證明i

=n+1時(shí)結(jié)論成立明）12/18/2019（歸納證24數(shù)學(xué)歸納法12/18/2019253.證明一個(gè)特性對(duì)所有正整數(shù)n成立特性對(duì)于1成立，（初始?xì)w納）如果對(duì)于所有的n

≥1時(shí)，特性對(duì)n成立，（歸納假設(shè)）證明：特性對(duì)n+1成立（歸納證明）2.

用數(shù)學(xué)歸納法證明：當(dāng)n

1時(shí)，12/18/201926()1

結(jié)論成立。2.證明：n

=1時(shí),

log1

=

0假設(shè)對(duì)所有的

n

1時(shí)，成立，證明成立。因?yàn)榧?2/18/201927作業(yè)112/18/20192811.用數(shù)學(xué)歸納法證明：當(dāng)n≥1時(shí)，12.用數(shù)學(xué)歸納法證明：2012年3月23日（周五）交第一次作業(yè)本章小結(jié)12/18/201929前言

算法分析的介紹，本課程的地位算法設(shè)計(jì)與分析是計(jì)算機(jī)專業(yè)中面向設(shè)計(jì)的、處于核心地位的且十分重要的專業(yè)基礎(chǔ)課。本課程的目的經(jīng)典的算法設(shè)計(jì)策略；用經(jīng)典的算法設(shè)計(jì)策略設(shè)計(jì)算法；分析算法效率的方法；算法正確性證