算法設(shè)計(jì)與分析：回顧

算法設(shè)計(jì)與分析什么是算法—定義輸入：有零個(gè)或多個(gè)外部量作為算法的輸入。輸出：算法產(chǎn)生至少一個(gè)量作為輸出。確定性：組成算法的每條指令清晰、無(wú)歧義。有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時(shí)間也有限。算法是解決問(wèn)題的方法或過(guò)程，嚴(yán)格地講是滿足下述性質(zhì)的指令序列?！癆lgorithms:acommonlanguagefornature,human,andcomputer.”

—AviWigderson什么是算法—

計(jì)數(shù)判斷一個(gè)byte里面有多少個(gè)bit的值為1？intCal(intiValue){while(iValue!=0){iReminder=iValue%2;if(iReminder==1)iCount++;iValue=iValue/2;

}returniCount;}如果這個(gè)子函數(shù)需要調(diào)用很多次，內(nèi)存空間足夠，怎樣提高性能？如果既想省時(shí)間，又想省空間，怎樣改進(jìn)？intiTables[256]={…};iCount=iTables[iValue];HashMapMaps;If(Maps.containsKey(Value)){Count=Maps.get(Value)}else{Maps.put(Value,newInteger(Cal(iValue)))}什么是算法—最大和連續(xù)子數(shù)列問(wèn)題描述:

給定一個(gè)整數(shù)數(shù)列{A1,A2,…,An}，求Ai+Ai+1+…+Aj-1+Aj的最大值，并確定對(duì)應(yīng)的子序列。如果所有的整數(shù)都是負(fù)數(shù)，那么最大連續(xù)子數(shù)列和為0。例如:{1,

-3,4,5}的最大子數(shù)列為{4,5}，因?yàn)?+5最大；{3,4,-5,8,-4}的最大子數(shù)列為{3,4,-5,8}，因?yàn)?+4-5+8最大為10；{4,3,-1,2}的最大子數(shù)列為{4,3,-1,2}，因?yàn)?+3-1+2最大為8。課程內(nèi)容算法復(fù)雜性枚舉策略遞歸與分治動(dòng)態(tài)規(guī)劃貪心算法搜索技術(shù)時(shí)間復(fù)雜度分析

枚舉算法確定枚舉對(duì)象

枚舉對(duì)象也可以理解為是問(wèn)題解的表達(dá)形式，一般需要用若干參數(shù)來(lái)描述參數(shù)之間需要相互獨(dú)立，而且參數(shù)數(shù)目越少，問(wèn)題解的搜索空間的維度也相應(yīng)地??；每個(gè)參數(shù)的取值范圍越小，問(wèn)題解的搜索空間也越小。逐一列舉可能解根據(jù)枚舉對(duì)象的參數(shù)構(gòu)造循環(huán)，一一列舉其表達(dá)式的每一種取值情況逐一驗(yàn)證可能解根據(jù)問(wèn)題解的要求，一一驗(yàn)證枚舉對(duì)象表達(dá)式的每一個(gè)取值，如果滿足條件，則采納它，否則，拋棄之大道至簡(jiǎn)百錢(qián)百雞、二分枚舉分治策略分治法所能解決的問(wèn)題特征：該問(wèn)題的規(guī)?？s小到一定的程度就可以容易地解決該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的divide-and-conquer(P){

if(|P|<=n0)adhoc(P);

//解決小規(guī)模的問(wèn)題

dividePintosmallersubinstancesP1,P2,...,Pk；//分解問(wèn)題

for

(i=1;i<=k;i++)

yi=divide-and-conquer(Pi);//遞歸的解各子問(wèn)題

returnmerge(y1,...,yk);

//將各子問(wèn)題的解合并為原問(wèn)題的解}治眾如治寡，分?jǐn)?shù)是也！合并排序、快速排序、二分查找動(dòng)態(tài)規(guī)劃分析最優(yōu)解的性質(zhì)，并刻劃其最優(yōu)子結(jié)構(gòu)特征確定狀態(tài)表示S(x1,x2,…)和狀態(tài)轉(zhuǎn)移方程，遞歸地定義最優(yōu)值確定狀態(tài)轉(zhuǎn)移順序，以自底向上的方式計(jì)算出最優(yōu)值根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解前事不忘，后事之師矩陣連乘、多段圖最短路徑、最長(zhǎng)公共子序列算法篇－貪心算法活動(dòng)安排問(wèn)題、哈夫曼編碼，最小生成樹(shù)貪心算法的三個(gè)邏輯步驟：分解

將原問(wèn)題求解過(guò)程劃分為連續(xù)的若干個(gè)決策階段決策

在每一個(gè)階段依據(jù)貪心策略進(jìn)行局部貪心決策，并縮小待求解問(wèn)題的規(guī)模合并

將各個(gè)階段的局部解合并為原問(wèn)題的一個(gè)全局可行解貪心算法也是一種基于子問(wèn)題思想的策略。貪心算法是一個(gè)分階段決策過(guò)程，在每個(gè)局部階段，貪心法都做出一個(gè)當(dāng)前最優(yōu)的局部決策，并期望通過(guò)每次所做的局部最優(yōu)決策產(chǎn)生一個(gè)全局最優(yōu)解。盲人爬山算法篇－搜索策略搜索算法的兩個(gè)邏輯步驟：定義問(wèn)題的解空間搜索解空間，并在搜索過(guò)程中用剪枝策略避免無(wú)效搜索搜索算法是一種通用的問(wèn)題求解方法：首先把問(wèn)題表示轉(zhuǎn)換為一個(gè)狀態(tài)空間圖，然后設(shè)計(jì)特定的圖遍歷方法在狀態(tài)空間中搜索問(wèn)題的解

基于枚舉策略的搜索深度優(yōu)先搜索廣度優(yōu)先搜索

優(yōu)化+枚舉的搜索回溯算法=深度優(yōu)先搜索+剪枝策略分支限界算法=廣度優(yōu)先搜索+剪枝策略

啟發(fā)式搜索，啟發(fā)式搜索是一種基于規(guī)則的優(yōu)化搜索算法優(yōu)化枚舉，提前判定人生如算法有人善“分治”再多再大的難題也如庖丁解牛