算法設計與分析什么是算法—定義輸入：有零個或多個外部量作為算法的輸入。輸出：算法產生至少一個量作為輸出。確定性：組成算法的每條指令清晰、無歧義。有限性：算法中每條指令的執行次數有限，執行每條指令的時間也有限。算法是解決問題的方法或過程，嚴格地講是滿足下述性質的指令序列。“Algorithms:acommonlanguagefornature,human,andcomputer.”

—AviWigderson什么是算法—

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

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

給定一個整數數列{A1,A2,…,An}，求Ai+Ai+1+…+Aj-1+Aj的最大值，并確定對應的子序列。如果所有的整數都是負數，那么最大連續子數列和為0。例如:{1,

-3,4,5}的最大子數列為{4,5}，因為4+5最大；{3,4,-5,8,-4}的最大子數列為{3,4,-5,8}，因為3+4-5+8最大為10；{4,3,-1,2}的最大子數列為{4,3,-1,2}，因為4+3-1+2最大為8。課程內容算法復雜性枚舉策略遞歸與分治動態規劃貪心算法搜索技術時間復雜度分析

枚舉算法確定枚舉對象

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

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

//解決小規模的問題

dividePintosmallersubinstancesP1,P2,...,Pk；//分解問題

for

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

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

returnmerge(y1,...,yk);

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

將原問題求解過程劃分為連續的若干個決策階段決策

在每一個階段依據貪心策略進行局部貪心決策，并縮小待求解問題的規模合并

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

基于枚舉策略的搜索深度優先搜索廣度優先搜索

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

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