算法設(shè)計(jì)與分析王喜鳳wxf80106@126.com課程學(xué)時(shí)總學(xué)時(shí)：24學(xué)時(shí)；其中講課：18學(xué)時(shí)；上機(jī)：6學(xué)時(shí)參考資料[1]王曉東.算法設(shè)計(jì)與分析（第二版）.清華大學(xué)出版社，2008.1[2]算法設(shè)計(jì)與分析習(xí)題解答王曉東編著清華大學(xué)出版社2006[3]SaraBaase等.計(jì)算機(jī)算法-設(shè)計(jì)與分析導(dǎo)論（英文第三版影印版）.高等教育出版社，2001.7Web資源,,…課程目標(biāo)—性質(zhì)、類型、地位專業(yè)基礎(chǔ)課選修課計(jì)算機(jī)科學(xué)的核心性質(zhì)類型地位課程目標(biāo)—教學(xué)目標(biāo)算法分析能力算法設(shè)計(jì)能力訓(xùn)練計(jì)算思維可用計(jì)算機(jī)有效解決常見(jiàn)實(shí)際問(wèn)題具體用處可從計(jì)算機(jī)角度，建立常見(jiàn)問(wèn)題的解決思路比賽：如ACM（ICPC）、TopCoder

考碩士(復(fù)試科目)或博士（考試科目）課程主要內(nèi)容第1章 算法引論第2章 遞歸與分治策略第3章 動(dòng)態(tài)規(guī)劃第4章 貪心算法第5章 回溯法第6章 分支限界法第7章 概率算法第8章 NP完全性理論第9章 近似算法第10章算法優(yōu)化策略第1章算法引論1.1 算法與程序1.2算法與數(shù)據(jù)結(jié)構(gòu)1.3表達(dá)算法的抽象機(jī)制1.4描述算法與算法設(shè)計(jì)1.5算法分析的基本原則1.6算法復(fù)雜性分析本章主要知識(shí)點(diǎn)：1.0算法概述很難給算法（algorithm）給出精確的定義。“算法是一組有窮的規(guī)則，它們規(guī)定了解決某一特定類型問(wèn)題的一系列運(yùn)算。”計(jì)算機(jī)科學(xué)中，算法已逐漸成了用計(jì)算機(jī)解一類問(wèn)題的精確、有效方法的代名詞。

課程目標(biāo)—地位1.1 算法與程序算法：是滿足下述性質(zhì)（特性）的指令序列。輸入：有零個(gè)或多個(gè)外部量作為算法的輸入。輸出：算法產(chǎn)生至少一個(gè)量作為輸出。確定性：組成算法的每條指令清晰、無(wú)歧義。有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時(shí)間也有限。程序：程序是算法的某種程序設(shè)計(jì)語(yǔ)言的描述。程序可以不滿足算法的性質(zhì)(4)即有限性。例如操作系統(tǒng)，是一個(gè)在無(wú)限循環(huán)中執(zhí)行的程序，因而不是一個(gè)算法。操作系統(tǒng)的各種任務(wù)可看成是單獨(dú)的問(wèn)題，每一個(gè)問(wèn)題由操作系統(tǒng)中的一個(gè)子程序通過(guò)特定的算法來(lái)實(shí)現(xiàn)。該子程序得到輸出結(jié)果后便終止。1.2 算法與數(shù)據(jù)結(jié)構(gòu)算法操作的對(duì)象是數(shù)據(jù)，數(shù)據(jù)間的邏輯關(guān)系、數(shù)據(jù)的存儲(chǔ)方式及處理方式就是數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。它與算法設(shè)計(jì)是緊密相關(guān)的。算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系不了解施加于數(shù)據(jù)上的算法就無(wú)法決定如何構(gòu)造數(shù)據(jù)，可以說(shuō)算法是數(shù)據(jù)結(jié)構(gòu)的靈魂；反之算法的結(jié)構(gòu)和選擇又常常在很大程度上依賴于數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)則是算法的基礎(chǔ)。算法＋數(shù)據(jù)結(jié)構(gòu)＝程序課程目標(biāo)—地位算法+數(shù)據(jù)結(jié)構(gòu)=程序武林大會(huì)兵器：刀、劍、棒課程目標(biāo)—地位算法+數(shù)據(jù)結(jié)構(gòu)=程序武林大會(huì)兵器：刀、劍、棒招式課程目標(biāo)—地位算法+數(shù)據(jù)結(jié)構(gòu)=程序武林大會(huì)兵器：刀、劍、棒招式1.3 表達(dá)算法的抽象機(jī)制從機(jī)器語(yǔ)言到高級(jí)語(yǔ)言的抽象高級(jí)程序設(shè)計(jì)語(yǔ)言的主要好處是：高級(jí)語(yǔ)言更接近算法語(yǔ)言，易學(xué)、易掌握，一般工程技術(shù)人員只需要幾周時(shí)間的培訓(xùn)就可以勝任程序員的工作；高級(jí)語(yǔ)言為程序員提供了結(jié)構(gòu)化程序設(shè)計(jì)的環(huán)境和工具，使得設(shè)計(jì)出來(lái)的程序可讀性好，可維護(hù)性強(qiáng)，可靠性高；高級(jí)語(yǔ)言不依賴于機(jī)器語(yǔ)言，與具體的計(jì)算機(jī)硬件關(guān)系不大，因而所寫出來(lái)的程序可植性好、重用率高；把繁瑣的事務(wù)交給編譯程序，所以自動(dòng)化程度高，開(kāi)發(fā)周期短，程序員可以集中時(shí)間和精力從事更重要的創(chuàng)造性勞動(dòng)，提高程序質(zhì)量。1.3 表達(dá)算法的抽象機(jī)制抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型是算法的一個(gè)數(shù)據(jù)模型連同定義在該模型上并作為算法構(gòu)件的一組運(yùn)算。抽象數(shù)據(jù)類型帶給算法設(shè)計(jì)的好處有：算法頂層設(shè)計(jì)與底層實(shí)現(xiàn)分離；算法設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)隔開(kāi)，允許數(shù)據(jù)結(jié)構(gòu)自由選擇；數(shù)據(jù)模型和該模型上的運(yùn)算統(tǒng)一在ADT中，便于空間和時(shí)間耗費(fèi)的折衷；用抽象數(shù)據(jù)類型表述的算法具有很好的可維護(hù)性；算法自然呈現(xiàn)模塊化；為自頂向下逐步求精和模塊化提供有效途徑和工具；算法結(jié)構(gòu)清晰，層次分明，便于算法正確性的證明和復(fù)雜性的分析。1.4 描述算法與算法設(shè)計(jì)描述算法可以有多種方式，如自然語(yǔ)言方式、圖形表格方式等。本書采用Java與自然語(yǔ)言相結(jié)合的方式；本人對(duì)語(yǔ)言不做任何限制：C++、C#、VB……1.4 描述算法與算法設(shè)計(jì)問(wèn)題求解(ProblemSolving)證明正確性分析算法設(shè)計(jì)程序理解問(wèn)題精確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)策略設(shè)計(jì)算法1.5 算法復(fù)雜性分析why？設(shè)一臺(tái)作109次/秒運(yùn)算（1G）的計(jì)算機(jī)的效率超過(guò)10億人同時(shí)工作。IBM研發(fā)單芯片超級(jí)計(jì)算機(jī)速度達(dá)1萬(wàn)億次/秒2003-9-1比如拿最簡(jiǎn)單例子，26個(gè)英文字母全排列，它的排列數(shù)為：26！≈4×1026以每年365天計(jì)算，共有

365×24×3600＝3.1536×107秒以每秒能完成109個(gè)排列的超高速電子計(jì)算機(jī)來(lái)做這項(xiàng)工作，需要4×1026/(3.1536×1016)≈1.2×1010年即使計(jì)算機(jī)運(yùn)行速度隨著技術(shù)的提高，恐怕也還是不可能實(shí)現(xiàn)的。因計(jì)算機(jī)的速度再提高也有它的極限。1.5 算法復(fù)雜性分析算法復(fù)雜性是算法運(yùn)行所需要的計(jì)算機(jī)資源量，需要的時(shí)間資源量稱為時(shí)間復(fù)雜性，需要的空間資源量稱為空間復(fù)雜性。這個(gè)量應(yīng)該是只依賴于問(wèn)題的規(guī)模(N)、算法的輸入(I)和算法本身的函數(shù)(A)。用C表示復(fù)雜性，那么，應(yīng)該有C=F(N,I,A)。一般把時(shí)間復(fù)雜性和空間復(fù)雜性分開(kāi)，并分別用T和S來(lái)表示，則有：T=T(N,I)和S=S(N,I)

。（通常，讓A隱含在復(fù)雜性函數(shù)名當(dāng)中）算法復(fù)雜性=算法所需要的計(jì)算機(jī)資源算法的時(shí)間復(fù)雜性T(n)；算法的空間復(fù)雜性S(n)。其中n是問(wèn)題的規(guī)模（輸入大小）。算法復(fù)雜度是指算法時(shí)間與問(wèn)題規(guī)模的關(guān)系1.5 算法復(fù)雜性分析最壞情況下的時(shí)間復(fù)雜性：k種元運(yùn)算，每種運(yùn)算的時(shí)間為ti，元運(yùn)算的次數(shù)為ei最好情況下的時(shí)間復(fù)雜性：平均情況下的時(shí)間復(fù)雜性：其中DN是規(guī)模為N的合法輸入的集合；I*是DN中使T(N,I*)達(dá)到Tmax(N)的合法輸入；是中使T(N,)達(dá)到Tmin(N)的合法輸入；而P(I)是在算法的應(yīng)用中出現(xiàn)輸入I的概率。1.5算法復(fù)雜性表達(dá)形式函數(shù)的漸進(jìn)性態(tài)與漸進(jìn)表達(dá)式：一般來(lái)說(shuō)，當(dāng)N單調(diào)增加且趨于∞時(shí)，T(N)也將單調(diào)增加趨于∞。對(duì)于T(N)，如果存在函數(shù)T'(N)，使得當(dāng)N→∞使有(T(N)-T'(N))/T(N)→0，那么我們就說(shuō)T'(N)是T(N)當(dāng)N→∞時(shí)的漸進(jìn)性態(tài)。在數(shù)學(xué)上，T'(N)是T(N)當(dāng)N→∞時(shí)的漸進(jìn)表達(dá)式。例如：3N2+4NlogN+7與3N2。1.5算法復(fù)雜性表達(dá)形式算法復(fù)雜性在漸近意義下的階：漸近意義下的記號(hào)：O設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)。O的定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)N≥N0時(shí)有f(N)≤Cg(N)，則稱函數(shù)f(N)當(dāng)N充分大時(shí)上有界，且g(N)是它的一個(gè)上界，記為f(N)=O(g(N))。即f(N)的階不高于g(N)的階。根據(jù)O的定義，容易證明它有如下運(yùn)算規(guī)則：O(f)+O(g)=O(max(f,g))；O(f)+O(g)=O(f+g)；O(f)O(g)=O(fg)；如果g(N)=O(f(N))，則O(f)+O(g)=O(f)；O(Cf(N))=O(f(N))，其中C是一個(gè)正的常數(shù)；f=O(f)。T（n）=3n+2=O（n）1.5算法復(fù)雜性表達(dá)形式規(guī)則Ｏ(f(n))+Ｏ(g(n))=Ｏ(max{f(n),g(n)})的證明：對(duì)于任意f1(n)=Ｏ(f(n))，存在正常數(shù)c1和自然數(shù)n1，使得對(duì)所有n≥n1，有f1(n)≤c1f(n)。類似地，對(duì)于任意g1(n)=Ｏ(g(n))，存在正常數(shù)c2和自然數(shù)n2，使得對(duì)所有n≥n2，有g(shù)1(n)≤c2g(n)。令c3=max{c1,c2}，n3=max{n1,n2}，

h(n)=max{f(n),g(n)}。則對(duì)所有的n≥n3，有

f1(n)+g1(n)≤c1f(n)+c2g(n)≤c3f(n)+c3g(n)=c3(f(n)+g(n))≤c32max{f(n),g(n)}

＝

2c3h(n)＝Ｏ(max{f(n),g(n)}).1.5算法的時(shí)間復(fù)雜性例1sum=0；

（一次）

for(i=1;i<=n;i++)

（n次）

for(j=1;j<=n;j++)（n2次）

sum++；

（n2次）

解：T(n)=2n2+n+1=O(n2)1.5算法的時(shí)間復(fù)雜性例1：a=0;

b=1;

①

for(i=1;i<=n;i++)②

{

s=a+b;

③

b=a;

④

a=s;

⑤

}

解：語(yǔ)句1的頻度：1＋1＝2,

語(yǔ)句2的頻度：n,

語(yǔ)句3的頻度：n-1,

語(yǔ)句4的頻度：n-1,

語(yǔ)句5的頻度：n-1,

T(n)=2+n+3(n-1)=4n-1=O(n)。1.5算法的時(shí)間復(fù)雜性例3i=1;

①while(i<=n)

i=i*2;②

解：語(yǔ)句1的頻度是1，設(shè)語(yǔ)句2的頻度是f(n)，

則：

2f(n)<=n;f(n)<=log2n，

取最大值f(n)=log2n,T(n)=O(log2n)。1.5最壞情況下的時(shí)間復(fù)雜性例4冒泡排序算法的基本步驟如下：voidBubbleSort(SeqListR)

{//R（l..n)是待排序的文件，采用自下向上掃描，對(duì)R做冒泡排序

inti，j；Booleanexchange；//交換標(biāo)志

for(i=1;i<n;i++){//最多做n-1趟排序

exchange=FALSE；//本趟排序開(kāi)始前，交換標(biāo)志應(yīng)為假

for(j=n-1;j>=i；j--)//對(duì)當(dāng)前無(wú)序區(qū)R[i..n]自下向上掃描

if(R[j+1].key<R[j].key){//交換記錄R[j+1]，R[j]交換；

exchange=TRUE；//發(fā)生了交換，故將交換標(biāo)志置為真

}

if(!exchange)//本趟排序未發(fā)生交換，提前終止算法

return；

}//endfor(外循環(huán))

}//BubbleSort當(dāng)輸入的數(shù)據(jù)已經(jīng)排好序，只要比較n-1次；當(dāng)輸入的數(shù)據(jù)是降序，要比較n(n-1)/2時(shí)間復(fù)雜度精確表示？？？T（n）=n2+2漸進(jìn)？？1.6算法分析的基本原則正確性定義：在給定有效輸入后，算法經(jīng)過(guò)有限時(shí)間的計(jì)算并產(chǎn)生正確的答案，就稱算法是正確的。正確性證明的內(nèi)容：方法的正確性證明——算法思路的正確性。證明一系列與算法的工作對(duì)象有關(guān)的引理、定理以及公式。//理論上是否正確程序的正確性證明——證明所給出的一系列指令確實(shí)做了所要求的工作。//實(shí)踐上是否正確程序正確性證明的方法：大型程序的正確性證明——可以將它分解為小的相互獨(dú)立的互不相交的模塊，分別驗(yàn)證。小模塊程序可以使用以下方法驗(yàn)證：數(shù)學(xué)歸納法等。1.6算法分析的基本原則工作量——時(shí)間復(fù)雜性分析計(jì)量工作量的標(biāo)準(zhǔn):對(duì)于給定問(wèn)題，該算法所執(zhí)行的基本運(yùn)算的次數(shù)。基本運(yùn)算的選擇：根據(jù)問(wèn)題選擇適當(dāng)?shù)幕具\(yùn)算。問(wèn)題基本運(yùn)算在表中查找x比較實(shí)矩陣相乘實(shí)數(shù)乘法排序比較遍歷二叉樹(shù)置指針1.6算法分析的基本原則占用空間——空間復(fù)雜性分析兩種占用：存儲(chǔ)程序和輸入數(shù)據(jù)的空間存儲(chǔ)中間結(jié)果或操作單元所占用空間——額外空間影響空間的主要因素：存儲(chǔ)程序的空間一般是常數(shù)(和輸入規(guī)模無(wú)關(guān))輸入數(shù)據(jù)的空間O(n)(n為輸入規(guī)模)空間復(fù)雜性考慮的是額外空間的大小1.6算法分析的基本原則簡(jiǎn)單性含義：算法簡(jiǎn)單，程序結(jié)構(gòu)簡(jiǎn)單。好處：容易驗(yàn)證正確性便于程序調(diào)試簡(jiǎn)單的算法效率不一定高。要在保證一定效率的前提下力求得到簡(jiǎn)單的算法。1.6算法分析的基本原則最優(yōu)性含義：指求解某類問(wèn)題中效率最高的算法兩種最優(yōu)性最壞情況：設(shè)A是解某個(gè)問(wèn)題的算法，如果在解這個(gè)問(wèn)題的算法類中沒(méi)有其它算法在最壞情況下的時(shí)間復(fù)雜性比A在最壞情況下的時(shí)間復(fù)雜性低，則稱A是解這個(gè)問(wèn)題在最壞情況下的最優(yōu)算法。平均情況：設(shè)A是解某個(gè)問(wèn)題的算法，如果在解這個(gè)問(wèn)題的算法類中沒(méi)有其它算法在平均情況下的時(shí)間復(fù)雜性比A在平均情況下的時(shí)間復(fù)雜性低，則稱A是解這個(gè)問(wèn)題在平均情況下的最優(yōu)算法。1.6算法分析的基本