第1章算法及基礎知識

算法設計與分析授課教師：王秋芬辦公地點：7307Email:學習算法的重要性算法與日常生活息息相關(guān)算法是程序設計的根基學習算法能夠提高分析問題的能力算法是推動計算機行業(yè)發(fā)展的關(guān)鍵研究算法是件快樂的事情

學習內(nèi)容算法及基礎知識貪心法分治法動態(tài)規(guī)劃搜索法隨機化算法線性規(guī)劃和網(wǎng)絡流數(shù)論算法及計算幾何算法NP完全性學習方法高度上（思想、策略、宏觀）邏輯上（在策略思想的指導下思考解決方法）實踐上（設計算法、分析算法）實質(zhì)：理論+實踐第一章算法及基礎知識目錄算法的基本概念算法設計的一般過程算法分析遞歸、基本數(shù)據(jù)結(jié)構(gòu)、常用數(shù)學公式第一章算法及基礎知識教學目標充分理解并掌握算法的相關(guān)概念理解算法設計的一般過程掌握對算法復雜性進行分析的方法掌握使用面向?qū)ο蟪绦蛟O計語言C++進行算法描述的方法掌握遞歸的概念及運用要點熟悉基本數(shù)據(jù)結(jié)構(gòu)和數(shù)學公式的概念及使用方法算法的定義、特性及描述方式算法的定義（舉例：求N個整數(shù)的和）對于計算機科學來說，算法指的是對特定問題求解步驟的一種描述，是若干條指令的有窮序列，且滿足算法的特性。算法的特性輸入、輸出、確定性、有限性、可行性描述方式自然語言、圖形（流程圖）、偽代碼、程序設計語言本書采用了面向?qū)ο蟪绦蛟O計語言C++思考：算法與程序的區(qū)別？算法與程序的區(qū)別算法是解決特定問題步驟的描述，程序是解決特定問題的功能代碼；算法一般不能直接到計算機上執(zhí)行，程序是可以直接在計算機上執(zhí)行的；程序是用某種計算機程序設計語言對算法翻譯的結(jié)果，算法是程序的精髓、靈魂。程序設計的實質(zhì)就是構(gòu)造解決問題的算法。算法設計的一般過程充分理解要解決的問題數(shù)學模型擬制算法詳細設計算法描述算法思路的正確性驗證算法分析算法的計算機實現(xiàn)和測試文檔資料的編制例：給定n個整數(shù)和一個整數(shù)C，問n個數(shù)中哪幾個數(shù)的和等于C。算法分析算法復雜性：算法運行時所需要的計算機資源的量時間復雜性、空間復雜性時間復雜性(T(n))分析方法事后統(tǒng)計法事前分析估算法影響時間復雜性的因素（板書：查找為例）問題規(guī)模n、輸入序列I、算法本身A影響空間復雜性的因素算法本身、輸入輸出數(shù)據(jù)、輔助變量三種情況下的復雜性

（例：查找）最好情況Tmin（N)1次最壞情況Tmax（N)N次平均情況Tavg（N)(N+1)/2空間復雜性S(n)存儲算法本身所占用的存儲空間；算法的輸入輸出數(shù)據(jù)所占用的存儲空間；算法在運行過程中所需的輔助變量占用的存儲空間，即輔助空間或臨時空間

算法漸近復雜性態(tài)設算法的運行時間為T(n)，如果存在T*(n)，使得

就稱T*(n)為算法的漸進性態(tài)或漸進時間復雜性。舉例說明（見教案）假設算法A的運行時間表達式T1(n)為：

T1(n)=30n4+20n3+40n2+46n+100算法B的運行時間表達式T2(n)為：

T2(n)=1000n3+50n2+78n+10思考：（1）算法A效率高還是算法B效率高？（2）為什么引入算法的漸進復雜性？

簡化漸進復雜性態(tài)的引入漸近意義下的記號（O、、）在下面的討論中，對所有n，f(n)

0，g(n)

0。（1）漸近上界記號O（舉例）O(g(n))={f(n)|存在正常數(shù)c和n0使得對所有n

n0有：0

f(n)

cg(n)}例：f(n)=logn2g(n)=5logn用O表示f(n)和g(n)常見幾類時間復雜性O(1)：常數(shù)階時間復雜性O(n)、O(n2)、O(n3)…：多項式階時間復雜性O(2n)、O(n!)和O(nn)：指數(shù)階時間復雜性O(nlogn)和O(logn)：對數(shù)階時間復雜性有用的規(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是一個正的常數(shù)；f=O(f)。（2）漸近下界記號

（舉例）

(g(n))={f(n)|存在正常數(shù)c和n0使得對所有n

n0有：0

cg(n)

f(n)}（3）漸近精確界記號

（舉例）

(g(n))={f(n)|存在正常數(shù)c1,c2和n0使得對所有n

n0有：c1g(n)

f(n)

c2g(n)}定理1：

(g(n))=O(g(n))

(g(n))算法的運行時間T(n)建立的依據(jù)非遞歸算法（a）選擇某種能夠用來衡量算法運行時間的依據(jù)；（b）依照該依據(jù)求出運行時間T(n)的表達式；（c）采用漸進符號表示T(n)；（d）獲得算法的漸進時間復雜性，進行進一步的比較和分析。例子11、求n個整數(shù)的最小值intarrayMax(inta[n]){intmax=a[0];for(inti=1;i<n;i++)if(a[i]>max)max=a[i];returnmax;}例子22、求n個整數(shù)中與給定K相等的元素。intfind(inta[n],intK){for(inti=0;i<n;i++)if(a[i]==K)break;returni;}空間復雜性與時間復雜性的分析方法類似遞歸子程序（或函數(shù)）直接調(diào)用自己或通過一系列調(diào)用語句間接調(diào)用自已，稱為遞歸。直接或間接調(diào)用自身的算法稱為遞歸算法。采用遞歸算法來求解問題的一般步驟：分析問題，尋找遞歸關(guān)系找出停止條件構(gòu)建函數(shù)體（設計遞歸算法，確定參數(shù)）n的階乘停止條件遞歸關(guān)系

停止條件與遞歸關(guān)系是遞歸函數(shù)的兩個要素，遞歸函數(shù)只有具備了這兩個要素，才能在有限次計算后得出結(jié)果。排列問題問題描述n個元素，它們的編號為1,2,…,n，排列問題的目的是生成這n個元素的全排列。算法設計思路將規(guī)模為n的排列問題轉(zhuǎn)化為規(guī)模為n-1的排列問題。將規(guī)模為n-1的排列問題轉(zhuǎn)化為規(guī)模為n-2的排列問題將問題規(guī)模一級一級降至1，1個元素的排列是它本身，此時到達遞推的停止條件。數(shù)組中的元素即為1個排列，然后進行回歸依次得到其它的排列。排列問題算法描述voidperm(intA[],intk,intn)//k:規(guī)模

{inti；

if(k==1)for(i=0;i<n;i++)cout<<A[i];elsefor(i=n-k;i<n;i++){swap(A[i],A[n-k]);perm(A,k-1,n);swap(A[i],A[n-k]);}}遞歸算法復雜性分析遞歸算法的時間復雜性分析決定采用哪個（或哪些）參數(shù)作為輸入規(guī)模的度量；找出對算法的運行時間貢獻最大的語句作為基本語句；檢查一下，對于相同規(guī)模的不同輸入，基本語句的執(zhí)行次數(shù)是否不同。如果不同，則需要從最好、最差及平均三種情況進行討論；對于選定的基本語句的執(zhí)行次數(shù)建立一個遞推關(guān)系式，并確定停止條件；通過計算該遞推關(guān)系式得到算法的漸進時間復雜性。遞歸算法的空間復雜性分析遞歸深度以排列問題為例分析遞歸算法的復雜性當k=1時，已構(gòu)成一個排列，第一個for循環(huán)需要執(zhí)行n次操作將排列輸出；當k=n時，第二個for循環(huán)的循環(huán)體，對perm(A,k-1,n)執(zhí)行n次調(diào)用。因此，排序算法perm對應的遞歸定義式為：采用后向代入法計算可得到通項公式：T(n)=nT(n-1)

=......

=n(n-1)(n-2)......2T(1)

=n!

所以，全排列算法perm的時間復雜性為O(n!)?；仡櫝Ｓ玫臄?shù)據(jù)結(jié)構(gòu)線性表樹圖集合算法漸近復雜性分析中常用數(shù)學公式（1）對數(shù)公式（2）組合公式（3）求和公式（4）向下取整和向上取整公式

（1）對數(shù)函數(shù)

logn=log2n;

lgn=log10n;

lnn=logen;

logkn=(logn)k;loglogn=log(logn);fora>0,b>0,c>0取整函數(shù)的若干性質(zhì)

x-1<x

x

x<x+1；

n/2