第一章 算法概述

高級(jí)算法設(shè)計(jì)與分析

第一章算法概述第一章算法概述1算法基本概念2插入算法分析舉例3復(fù)雜度分析漸近記號(hào)常用函數(shù)1算法基本概念—什么是算法？算法的形式定義可以看作是任何一個(gè)定義好（有窮/確定/可行）的計(jì)算過(guò)程，以一個(gè)或一些值作為輸入，產(chǎn)生出一個(gè)或一組值作為輸出（問(wèn)題陳述）?！癱omputer”problemalgorithminputoutput1算法基本概念—算法1-4算法是若干指令的有窮序列，滿足性質(zhì)：輸入：有外部提供的量作為算法的輸入。輸出：算法產(chǎn)生至少一個(gè)量作為輸出。確定性：組成算法的每條指令是清晰，無(wú)歧義的。有限性：算法中每條指令的執(zhí)行次數(shù)是有限的，執(zhí)行每條指令的時(shí)間也是有限的?？尚行?算法是能夠有效解決問(wèn)題的1算法基本概念—問(wèn)題求解過(guò)程1-5證明正確性分析算法設(shè)計(jì)程序理解問(wèn)題精確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)策略設(shè)計(jì)算法1算法基本概念—算法分析(1)

《數(shù)據(jù)結(jié)構(gòu)與算法》課講述過(guò)一部分算法分析基礎(chǔ)；判斷算法“好”與”不好”?正確性時(shí)間效率空間效率算法分析是指對(duì)算法所需的時(shí)間和空間等資源進(jìn)行預(yù)測(cè)途徑:理論/數(shù)學(xué)上的分析經(jīng)驗(yàn)/計(jì)算機(jī)上的執(zhí)行情況算法復(fù)雜性=算法所需要的計(jì)算機(jī)資源；算法的時(shí)間復(fù)雜性T(n)，其中n是問(wèn)題的輸入規(guī)模。最壞情況下的時(shí)間復(fù)雜性

Tmax(n)=max{T(I)|size(I)=n}最好情況下的時(shí)間復(fù)雜性

Tmin(n)=min{T(I)|size(I)=n}平均情況下的時(shí)間復(fù)雜性

Tavg(n)=其中I是問(wèn)題的規(guī)模為n的實(shí)例，p(I)是實(shí)例I出現(xiàn)的概率算法的空間復(fù)雜性S(n)；1算法基本概念—算法分析(2)

1算法基本概念—算法分析(3)

算法運(yùn)行時(shí)間的階較簡(jiǎn)明地刻畫了一個(gè)算法的效率，并作為不同算法進(jìn)行比較的工具；當(dāng)輸入規(guī)模足夠大時(shí)，運(yùn)行時(shí)間中的低階項(xiàng)和最高次項(xiàng)的常數(shù)系數(shù)可以忽略；輸入規(guī)模足夠大到只需考慮運(yùn)行時(shí)間的增長(zhǎng)量級(jí)時(shí)，研究的算法效率即為漸近效率。亦即，我們只關(guān)心從極限的角度考慮運(yùn)行時(shí)間如何隨輸入規(guī)模的增長(zhǎng)而增長(zhǎng)。漸近效率更高的算法，對(duì)大規(guī)模的輸入是更好的。（對(duì)小規(guī)模的輸入則不一定?。?插入排序(1)輸入:n個(gè)數(shù)的一個(gè)序列<a1,a2,…,an>.輸出:

輸入序列的一個(gè)排列<a'1,a'2,…,a'n>，滿足a'1

￡

a'2

￡…

￡

a'n排序問(wèn)題2插入排序(2)算法偽代碼2分析插入排序算法(1)假定一種單處理器計(jì)算模型—隨機(jī)訪問(wèn)模型(Random-AccessMachine,

RAM)：指令一條接一條執(zhí)行，沒有并發(fā)操作。簡(jiǎn)單起見，假設(shè)每條指令所需時(shí)間均為常量。算術(shù)指令：加法、減法、乘法、除法、取余，向下取整、向上取整

數(shù)據(jù)移動(dòng)指令：裝入、存儲(chǔ)、復(fù)制控制指令：條件與無(wú)條件轉(zhuǎn)移、子程序調(diào)用與返回。RAM模型中的數(shù)據(jù)類型有整數(shù)型和浮點(diǎn)實(shí)數(shù)型。不考慮內(nèi)存層次的影響。2分析插入排序算法(2)一個(gè)算法的運(yùn)行時(shí)間是指在特定輸入時(shí)所執(zhí)行的基本操作數(shù)或步數(shù)?；静僮鳎?/p>

對(duì)算法運(yùn)行時(shí)間影響最大的操作，通常是算法最內(nèi)層循環(huán)中最費(fèi)時(shí)的操作。定義“步”的概念盡量獨(dú)立于機(jī)器。算法的運(yùn)行時(shí)間嚴(yán)重依賴于問(wèn)題的輸入規(guī)模。一般地，算法的運(yùn)行時(shí)間與輸入規(guī)模同步增長(zhǎng)。即使規(guī)模相同的兩個(gè)不同輸入，其運(yùn)行時(shí)間也可能差別很大例如：當(dāng)插入排序在處理已排序好的n個(gè)元素?cái)?shù)組和逆序排列的n個(gè)元素?cái)?shù)組時(shí)。2分析插入排序算法(3)假定每次執(zhí)行第i行所花的時(shí)間都是常量ci；對(duì)

j=2,3,…n,假設(shè)tj表示對(duì)那個(gè)值j執(zhí)行while循環(huán)測(cè)試的次數(shù)。當(dāng)一個(gè)for或while循環(huán)按通常的方式（由于循環(huán)頭中的測(cè)試）退出時(shí)，執(zhí)行測(cè)試的次數(shù)比執(zhí)行循環(huán)體的次數(shù)多1。2分析插入排序算法(4)插入排序的運(yùn)行時(shí)間:

運(yùn)行時(shí)間取決于tj

的值，其隨輸入問(wèn)題的情況而定.

數(shù)組已排好序線性函數(shù)2分析插入排序算法(5)最壞情況:在整個(gè)循環(huán)測(cè)試中，總是A[i]>key。必須將每個(gè)元素A[j]與整個(gè)已排序子數(shù)組A[1..j]中的每個(gè)元素進(jìn)行比較。

tj=j.

數(shù)組已逆序排好T(n)表示為an2+bn+c，其中常量a,

b和c

依賴于語(yǔ)句代價(jià)ci二次函數(shù)2分析插入排序算法(6)最壞情況與平均情況分析：通常關(guān)心最壞情況運(yùn)行時(shí)間：算法的最壞情況運(yùn)行時(shí)間給出了任何輸入的運(yùn)行時(shí)間的一個(gè)上界對(duì)某些算法，最壞情況經(jīng)常出現(xiàn)有時(shí)定義平均情況較為困難平均情況的時(shí)間復(fù)雜度往往與最壞情況一樣例子:對(duì)插入排序而言，平均情況運(yùn)行時(shí)間仍是n的二次函數(shù)平均情況分析：通常假定一個(gè)特定規(guī)模下的所有輸入的“平均性”都是一樣的也可以采用隨機(jī)算法強(qiáng)制達(dá)到平均。2分析插入排序算法(7)tj理解為隨機(jī)變量參看最壞情況下tj=j，T(n)表示為an2+bn+c

，則平均情況下的運(yùn)行時(shí)間仍是n的二次函數(shù)3漸近記號(hào)—O記號(hào)(1)漸近上界記號(hào)O(big-oh)漸近地給出了一個(gè)函數(shù)在常量因子內(nèi)的上界:

O(g(n))={f(n):存在正常量c和n0，使得對(duì)所有n≥n0，

有0≤f(n)≤cg(n)}舉例:g(n)=n2,n2+n,n2+1000n,1000n2+1000n,5000n,200n1.9f(n)=

(g(n))蘊(yùn)含著f(n)=O(g(n))O可用于標(biāo)識(shí)最壞情況運(yùn)行時(shí)間3漸近記號(hào)—O記號(hào)(2)練習(xí):下列哪些關(guān)系是正確的?1000000n2

O(n2)√(n–1)n/2

O(n2)√

n/2

O(n2)×

n2

O(n)×lgn2

O(lgn)√lg2n

O(lgn)×3漸近記號(hào)—

記號(hào)(1)漸近下界記號(hào)

(big-omege)漸近地給出了一個(gè)函數(shù)在常量因子內(nèi)的下界:

(g(n))={f(n):存在正常量c和n0，使得對(duì)所有n

n0

有

0≤cg(n)≤f(n)foralln≥n0}舉例：g(n)=n2,1000n2+1000n,1000n2–1000n,n3,200n2.1)f(n)=

(g(n))蘊(yùn)含著f(n)=

(g(n))

可用于標(biāo)識(shí)最佳情況運(yùn)行時(shí)間插入排序的運(yùn)行時(shí)間?(n)和

O(n2)3漸近記號(hào)—

記號(hào)(2)練習(xí):下列哪些關(guān)系是正確的?1000000n2

W(n2)√(n–1)n/2

W(n2)√

n/2

W(n2)lgn2

W(lgn)lg2n

W(lgn)n2

W(n)3漸近記號(hào)—

記號(hào)(1)漸近緊確界記號(hào)

(big-theta)漸近地給出了一個(gè)函數(shù)的上界和下界:

(g(n))={f(n):存在正常量c1,c2和n0，使得對(duì)所有n≥n0，

有0≤c1g(n)≤f(n)≤c2g(n)}舉例:n2/2–2n

(n2),滿足

c1=1/4,c2=1/2和n0=8。3漸近記號(hào)—

記號(hào)(2)f(n)=

(g(n))的確切意義是：f(n)

(g(n))。即對(duì)任一函數(shù)f(n)滿足上述條件時(shí)，則f(n)屬于集合

(g(n))；

(g(n))的定義要求其每個(gè)元素漸近非負(fù)（當(dāng)n趨于無(wú)窮大時(shí),f(n)和g(n)都非負(fù)），這也要求g(n)本身是漸近非負(fù)的（其他記號(hào)也是如此）。

(g(n))中的所有函數(shù)具有相同的最高階項(xiàng)。原理：f(n)

(g(n))，當(dāng)且僅當(dāng)f(n)

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

(g(n))3漸近記號(hào)—

記號(hào)(3)形式化證明n2/2-3n=

(n2)即確定正常數(shù)c1,c2和n0，使得對(duì)所有n

≥

n0，有：用n2除不等式得：右邊不等式在n

≥1，c2≥1/2時(shí)成立，左邊不等式在n7，c1

1/14時(shí)成立，選c1=1/14，c2=1/2，n0=7時(shí)上式即可成立。3漸近記號(hào)—

記號(hào)(4)練習(xí):下列哪些關(guān)系是正確的?1000000n2

(n2)(n–1)n/2

(n2)

n/2

(n2)lgn2

(lgn)lg2n

(lgn)n2

(n)3漸近記號(hào)—o記號(hào)非漸近緊確上界記號(hào)o

(小-oh)o(g(n))={f(n)|對(duì)于任何正常量c>0，存在常量n0>0使得對(duì)所有n

n0，有0

f(n)<cg(n)}舉例：5n

=o(n2)；盡管5n2=

O(n2)，但5n2

≠o(n2)若f(n)=o(g(n))，那么n當(dāng)趨于無(wú)窮時(shí)，f(n)相對(duì)于g(n)變得微不足道3漸近記號(hào)—

記號(hào)非漸近緊確下界記號(hào)

(小-omege)

(g(n))={f(n)|對(duì)于任何正常量c>0，存在常量n0>0使得對(duì)所有n

n0，有0

cg(n)

<f(n)}舉例：5n2

=

(n)；盡管5n2=

(n2)，但5n2

≠

(n2)。若f(n)=

(g(n))，那么n當(dāng)趨于無(wú)窮時(shí)，f(n)相對(duì)于g(n)變得任意大了f(n)

(g(n))當(dāng)且僅當(dāng)

g(n)

o(f(n))例1

，因此

3漸近記號(hào)—極限(1)用極限去定義漸近符號(hào)：

3漸近記號(hào)—極限(2)洛必達(dá)法則(L’Hopital’sRule)：

nk

o(2n)

lnn=o(na)，對(duì)任意a>0

nlnn

o(n2)3漸近記號(hào)—性質(zhì)(1)傳遞性:f(n)=O(g(n))且

g(n)=O(h(n)) 蘊(yùn)含f(n)=O(h(n))f(n)=

(g(n))且g(n)=

(h(n))

蘊(yùn)含f(n)=

(h(n))f(n)=

(g(n))且g(n)=

(h(n))

蘊(yùn)含f(n)=

(h(n))f(n)=o(g(n))且g(n)=o(h(n))

蘊(yùn)含f(n)=o(h(n))f(n)=

(g(n))且g(n)=

(h(n))

蘊(yùn)含f(n)=

(h(n))自反性:f(n)=O(f(n))f(n)=

(f(n))f(n)=

(f(n))注意：o

和

不具自反性3漸近記號(hào)—性質(zhì)(2)對(duì)稱性:f(n)=

(g(n))當(dāng)且僅當(dāng)g(n)=

(f(n)).轉(zhuǎn)置對(duì)稱性:f(n)=O(g(n))當(dāng)且僅當(dāng)g(n)=

(f(n)).f(n)=o(g(n))當(dāng)且僅當(dāng)g(n)=

(f(n)).漸近符號(hào)算術(shù)符號(hào)O≤

≥

=o<

>3漸近記號(hào)—性質(zhì)(3)單調(diào)性：?jiǎn)握{(diào)遞增：若m

n蘊(yùn)含f(m)

f(n)單調(diào)遞減：若m

n蘊(yùn)含f(m)

f(n)嚴(yán)格遞增：若m<n蘊(yùn)含f(m)<f(n)嚴(yán)格遞減：若m<n蘊(yùn)含f(m)>f(n)3漸近記號(hào)—性質(zhì)(4)定理如果t1(n)

∈O(g1(n))并且t2(n)

∈O(g2(n))，則

t1(n)+t2(n)

∈O(max{(g1(n),g2(n)})對(duì)于符號(hào)Ω和Θ，該定理也成立。該定理表明：當(dāng)算法由兩個(gè)連續(xù)執(zhí)行部分組成時(shí)，該算法的整體效率由具有較大增長(zhǎng)次數(shù)的那部分所決定，即效率較差的部分決定例子：0.5(n(n-1))∈O(n2)；0.5(n(n-1))=0.5n2-0.5n；0.5n2∈O(n2)3漸近記號(hào)—基本的效率類型(1)1常量logn對(duì)數(shù)n線性nlognnlognn2平方n3立方2n指數(shù)n!階乘排在前面的復(fù)雜性類型是算法設(shè)計(jì)追求的目標(biāo)。3漸近記號(hào)—基本的效率類型(1)排在前面的復(fù)雜性類型是算法設(shè)計(jì)追求的目標(biāo)。3漸近記號(hào)—基本的效率類型(2)3漸近記號(hào)—常用函數(shù)(1)向下取整與向上取整：底：小于或等于實(shí)數(shù)x的最大整數(shù)，

x頂：大于或等于實(shí)數(shù)x的最大整數(shù)，

x

對(duì)任意實(shí)數(shù)x：x–1<

x

x

x

<x+1對(duì)任意整數(shù)n：

n/2+

n/2=n對(duì)任意實(shí)數(shù)x和整數(shù)a≠0，b≠0：

x/a/b=x/ab

x/a/b=x/ab

向下取整函數(shù)和向上取整函數(shù)是單調(diào)遞增的；3漸近記號(hào)—常用函數(shù)(1)多項(xiàng)式：給定一個(gè)非負(fù)整數(shù)d，n的d次多項(xiàng)式是具有如下形式的函數(shù)：

其中常量ai是多項(xiàng)式的系數(shù)且ad

≠0。一個(gè)多項(xiàng)式是漸近正的，當(dāng)且僅當(dāng)ad

>0對(duì)一個(gè)d次的漸近正多項(xiàng)式p(n)，有p(n)=

(nd)。對(duì)函數(shù)na

，當(dāng)a

0時(shí)單調(diào)增，a

0時(shí)單調(diào)減。若對(duì)某個(gè)常量k，使f(n)=O(nk)，則稱函數(shù)f(n)是多項(xiàng)式有界的。3漸近記號(hào)—常用函數(shù)(1)指數(shù)式：對(duì)任意a>0，m和n，有恒等式：a0=1（并假設(shè)00=1）a1=aa-1=1/a(am)n

=amn(am)n

=(an)maman=am+n對(duì)所有n和a

1，函數(shù)an單調(diào)遞增3漸近記號(hào)—常用函數(shù)(1)指數(shù)式（續(xù)）：對(duì)任意常數(shù)a和b，且a>1，有：即：nb=o(an)，即任意正的指數(shù)函數(shù)較任意的多項(xiàng)式增長(zhǎng)更快。對(duì)所有實(shí)數(shù)x，有（e表示2.71828，!表示階乘函數(shù)）由上，得到不等式：ex

1+x(x=0時(shí)等號(hào)成立)當(dāng)x

0時(shí)，ex

1+x，表示為：ex=1+x+

(x2)對(duì)所有x，有3漸近記號(hào)—常用函數(shù)(1)對(duì)數(shù)記號(hào)：lgn=log2n（以2為底的對(duì)數(shù)）lnn=logen（自然對(duì)數(shù)）lgkn=(lgn)k（取冪）lglgn=lg(lgn)（復(fù)合）lgn+k表示(lgn)+k而不是lg(n+k)對(duì)于n>0和b>1，logbn嚴(yán)格遞增3漸近記號(hào)—常用函數(shù)(1)對(duì)數(shù)式（續(xù)）：對(duì)任意的實(shí)數(shù)a>0，b>0，c>0和n：因?yàn)楦淖儗?duì)數(shù)的底只是相差一個(gè)常數(shù)因子，故當(dāng)系數(shù)不重要時(shí)即寫為lgn，類似于O記號(hào)3漸近記號(hào)—常用函數(shù)(1)對(duì)數(shù)式（續(xù)）：當(dāng)|x|<1時(shí)，ln(1+x)的一個(gè)簡(jiǎn)單的級(jí)數(shù)展開為：當(dāng)x>-1時(shí)，有不等式(x=0時(shí)等號(hào)成立)對(duì)于某個(gè)常量k，如果f(n)=O(lgkn)，則稱函數(shù)多對(duì)數(shù)有界的將中用lgn替代n和2a替代a，得：即：lgbn=o(na)，即任意正的多項(xiàng)式函數(shù)較多項(xiàng)對(duì)數(shù)函數(shù)增長(zhǎng)更快。3漸近記號(hào)—常用函數(shù)(1)斯特林(Stirling)近似公式：可以推出

階乘：n!定義為對(duì)所有整數(shù)n

0：因此，n!=1·2·····nn!的一個(gè)弱上界為：n!

nn公式給出了n!的更緊確的上下界3漸近記號(hào)—常用函數(shù)(1)階乘（續(xù)）根據(jù)斯特林近似公式有：n!=o(nn)

n!=

(2n)lg(n!)=

(nlgn)對(duì)所有n，下列界也成立：其中3漸近記號(hào)—常用函數(shù)(1)多重對(duì)數(shù)函數(shù)：用記號(hào)lg*n來(lái)表示多重對(duì)數(shù)，其定義為：

請(qǐng)注意區(qū)分lg(i)n與lgi

n

：lg*2=1lg*4=2lg*16=3lg*65536=4lg*(265536)=5（很少能遇到lg*n>5的n）lg*n是一種增長(zhǎng)很慢的函數(shù)斐波那契數(shù)：一對(duì)兔子，從出生后第3個(gè)月起每個(gè)月都生一對(duì)兔子。小兔子長(zhǎng)到第3個(gè)月后每個(gè)月又生一對(duì)兔子。假如兔子都不死，請(qǐng)問(wèn)第1個(gè)月出生的一對(duì)兔子，第n個(gè)月有多少只兔子？分析：第一個(gè)月：一對(duì)兔子，第二個(gè)月：一對(duì)兔子，第三個(gè)月：上個(gè)月的一對(duì)兔子+第一個(gè)月兔子新出生的一對(duì)兔子=2對(duì)兔子第n個(gè)月F（n）=上個(gè)月（n-1月）的兔子數(shù)F（n-1）+上上個(gè)月（n-2月）新出生的兔子這個(gè)月又生出的兔子數(shù)F（n-2）斐波那契數(shù)：遞歸定義：（兔子繁殖問(wèn)題）F0=0,F1=1,Fi=Fi-1+Fi-2，i

2斐波那契序列：0,1,1,2,3,5,8,13,21,34,…由遞推公式，得知特征方程為：x2=x+1,求得根為：存在：代入F0=0,F1=1,求得：例:確定是否所有元素相互不同例2：考慮元素唯一性問(wèn)題的效率50輸入規(guī)模：數(shù)組元素n基本操作：比較除了和n有關(guān)外，還取決于數(shù)組中是否有相同的元素，以及它們?cè)跀?shù)組中的位置必須研究其最優(yōu)，平均和最差效率對(duì)最內(nèi)層的循環(huán)，有兩種類型的最差輸入：不包括相同元素的數(shù)組，或者最后兩個(gè)元素是唯一一對(duì)相同元素的數(shù)組。例：考慮元素唯一性問(wèn)題的效率51這個(gè)結(jié)果是完全可以預(yù)測(cè)的：在最壞的情況下，對(duì)于n個(gè)元素的所有n(n-1)/2對(duì)兩兩組合，該算法都要比較一遍。假如你面前有一堵朝兩個(gè)方向無(wú)限延伸的墻，墻上有一扇門，但你不知道門離你有多遠(yuǎn)，也不知道門在哪個(gè)方向。你只有走到門前才能看到它。假設(shè)從當(dāng)前位置到門要走n（n未知）步，請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，使你最多走O(n)步就能遇到門。例：找到我的門52n步先向右走1步；如果途中沒遇到門，再向左走2步；如果途中沒遇到門，再向右走4步；如果途中沒遇到門，再向左走8步；……

直到找到門為止。

53習(xí)題講解以向右的方向?yàn)檎?，左向的方向?yàn)樨?fù)；用f(i)表示第i次行至的位置，f(i)=(-2)(i)，其中i=0,1,2…,k；f(0)=1,f(1)=-2,f(2)=4,f(3)=-8,…假設(shè)在第k次行走的路途中找到了門，若k為偶數(shù)