算法及其基礎(chǔ)詳解演示文稿

算法及其基礎(chǔ)詳解演示文稿當(dāng)前第1頁\共有38頁\編于星期二\12點(diǎn)（優(yōu)選）算法及其基礎(chǔ)當(dāng)前第2頁\共有38頁\編于星期二\12點(diǎn)本章的要點(diǎn)與難點(diǎn)要點(diǎn):

理解算法的概念。程序與算法的區(qū)別和聯(lián)系；理解算法設(shè)計(jì)的一般過程；掌握用C++/JAVA語言以及偽代碼描述算法的方法；掌握算法的計(jì)算復(fù)雜性概念及分析。難點(diǎn):算法的計(jì)算復(fù)雜性（主要指時(shí)間復(fù)雜性）分析。當(dāng)前第3頁\共有38頁\編于星期二\12點(diǎn)1.1引子–排序問題排序問題描述：輸入：數(shù)字序列X=<a1,a2,…,an>輸出：一個排列X‘=<a‘1,a‘2,…,a‘n>，數(shù)字序列X和排列X‘之間為滿射或一一映射（即元素一一對應(yīng)），并且有a‘1≤a‘2≤…≤a‘n（元素間非減序）。例如：輸入：8,2,4,9,3,6輸出：2,3,4,6,8,9排序方法：冒泡、插入、歸并、二叉樹、桶排序等。穩(wěn)定的；選擇、Shell、堆、快速、組合排序等，不穩(wěn)定的。當(dāng)前第4頁\共有38頁\編于星期二\12點(diǎn)1.1引子–插入排序原理：通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。偽代碼：INSERTION-SORT(A,n)//A[1..n]forj=2tondokey=A[j]i=j-1

whilei>0andA[i]>keydoA[i+1]=A[i]i=i-1A[i+1]=key當(dāng)前第5頁\共有38頁\編于星期二\12點(diǎn)1.1引子–插入排序示例：當(dāng)前第6頁\共有38頁\編于星期二\12點(diǎn)1.1引子–插入排序證明–基于循環(huán)不變式(LoopInvariant)：循環(huán)不變式：在每次循環(huán)迭代之前，子數(shù)組A[1..j-1]已包含了最初位于A[1..j-1]、但已排好序的各個元素。初始化：第一輪迭代之前（即j=2），子數(shù)組A[1..j-1]（即A[1]）顯然保持了循環(huán)不變式；保持：假設(shè)第j次迭代之前循環(huán)不變式為真。該算法的第j次操作只是將A[j]與已有序的A[1..j-1]中的元素進(jìn)行比較，找到合適位置并插入。j+1次迭代之前，很顯然A[1..(j+1)-1]也保持了循環(huán)不變式；終止：j=n+1時(shí)，顯然A[1..(n+1)-1]（即A[1..n]）已包含了最初位于A[1..n]、且已排好序的各個元素。當(dāng)前第7頁\共有38頁\編于星期二\12點(diǎn)1.1引子–插入排序運(yùn)行時(shí)間分析：最壞情況：T(n)=O(n2)。，算術(shù)級數(shù)。已非升序排序；平均情況：T(n)=O(n2)。

，算術(shù)級數(shù)；最好情況：T(n)=O(n)。，已升序排序。當(dāng)前第8頁\共有38頁\編于星期二\12點(diǎn)1.1引子–歸并排序原理：基于分而治之思想，遞歸地把待排序序列分解為若干子序列并進(jìn)行排序，再把已排序的子序列合并為整體有序序列，最終實(shí)現(xiàn)全序列的有序。偽代碼：MERGE-SORT(A,low,high)//A[1..n]iflow<highthenmid=(low+high)/2MERGE-SORT(A,low,mid)MERGE-SORT(A,mid+1,high)MERGE(A,low,mid,high)當(dāng)前第9頁\共有38頁\編于星期二\12點(diǎn)1.1引子–歸并排序示例MERGE-SORT：當(dāng)前第10頁\共有38頁\編于星期二\12點(diǎn)1.1引子–歸并排序(MERGE)MERGE：當(dāng)前第11頁\共有38頁\編于星期二\12點(diǎn)1.1引子–歸并排序證明：可以嘗試采用循環(huán)不變式自行證明，這里略。當(dāng)前第12頁\共有38頁\編于星期二\12點(diǎn)1.1引子–歸并排序運(yùn)行時(shí)間分析：當(dāng)前第13頁\共有38頁\編于星期二\12點(diǎn)算法(Algorithm)：對于計(jì)算機(jī)科學(xué)來說，算法指的是對特定問題求解步驟的一種描述，是若干條指令的有窮序列。

算法的特性：輸入（0個或多個）、輸出（至少1個）、確定性（無歧義）、有限性、可行性。描述方式：自然語言、圖形、程序設(shè)計(jì)語言、偽代碼本書采用了面向?qū)ο蟪绦蛟O(shè)計(jì)語言C++，講授時(shí)采用偽代碼。算法與程序的區(qū)別？1.2算法的基本概念–算法當(dāng)前第14頁\共有38頁\編于星期二\12點(diǎn)程序(Program)程序是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)；程序可以不滿足算法的性質(zhì)(4)。例如：操作系統(tǒng)是一個在無限循環(huán)中執(zhí)行的程序，因而其不是一個算法；操作系統(tǒng)的各種任務(wù)：可看成是單獨(dú)的問題，每一個問題由操作系統(tǒng)中的一個子程序通過特定的算法來實(shí)現(xiàn)。1.2算法的基本概念–程序當(dāng)前第15頁\共有38頁\編于星期二\12點(diǎn)會場安排問題、單源最短路徑、哈夫曼編碼、最小生成樹排序與查找、循環(huán)賽日程表最長公共子序列、矩陣連乘、凸多邊形最優(yōu)三角剖分、加工順序等N后、最大團(tuán)、圖的m著色0-1背包、TSP、布線問題等等1.2算法的基本概念–經(jīng)典問題當(dāng)前第16頁\共有38頁\編于星期二\12點(diǎn)1.2算法的基本概念–拼圖游戲當(dāng)前第17頁\共有38頁\編于星期二\12點(diǎn)在n×n格的棋盤上放置彼此不受攻擊的n個皇后：按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子；n后問題等價(jià)于在n×n格的棋盤上放置n個皇后，任何2個皇后不放在同一行或同一列或同一斜線上。1234567812345678QQQQQQQQ1.2算法的基本概念–N后問題當(dāng)前第18頁\共有38頁\編于星期二\12點(diǎn)1.2算法的基本概念–0-1背包問題當(dāng)前第19頁\共有38頁\編于星期二\12點(diǎn)起點(diǎn)

XXXXXXXXXXXXXXXXXXXX終點(diǎn)XXXXX1.2算法的基本概念–布線問題當(dāng)前第20頁\共有38頁\編于星期二\12點(diǎn)1.3算法設(shè)計(jì)的一般過程當(dāng)前第21頁\共有38頁\編于星期二\12點(diǎn)算法復(fù)雜性（亦稱算法復(fù)雜度）為算法運(yùn)行時(shí)所需計(jì)算機(jī)資源的度量：時(shí)間復(fù)雜性（影響因素包括問題規(guī)模n、輸入序列I、算法本身A）：T(n,I,A)T(n)空間復(fù)雜性（影響因素包括輸入輸出數(shù)據(jù)IO、輔助變量V、算法本身A）：S(IO,V,A)S(V)很顯然：算法所需資源越多，算法的復(fù)雜性就越高；算法所需資源越少，算法的復(fù)雜性就越低。1.4算法分析–算法復(fù)雜性當(dāng)前第22頁\共有38頁\編于星期二\12點(diǎn)算法分析：對算法的時(shí)間復(fù)雜性和空間復(fù)雜性進(jìn)行分析，這里主要還是指對算法的時(shí)間復(fù)雜性的分析。方法：事后統(tǒng)計(jì)和事前分析算法分析的意義：算法設(shè)計(jì)：復(fù)雜性盡可能的低；算法選用：選擇復(fù)雜性最低的算法；算法改進(jìn)：算法分析有助于算法的改進(jìn)。1.4算法分析當(dāng)前第23頁\共有38頁\編于星期二\12點(diǎn)影響算法運(yùn)行時(shí)間的因素（除算法本身外）：機(jī)器；采用語言及編譯程序；編程能力等。算法分析無需具體時(shí)間（精確或近似）：針對同一問題不同算法的比較，相對而非絕對；應(yīng)該獨(dú)立于機(jī)器及實(shí)現(xiàn)語言；無論科技如何發(fā)展，其運(yùn)行時(shí)間的測度應(yīng)始終成立；關(guān)心的是大的問題規(guī)模時(shí)的運(yùn)行情況。漸近復(fù)雜性1.4算法分析–當(dāng)前第24頁\共有38頁\編于星期二\12點(diǎn)算法漸近復(fù)雜性態(tài)：設(shè)算法的運(yùn)行時(shí)間為T(n)，如果存在T*(n)，使得

就稱T*(n)為算法的漸近性態(tài)或漸近時(shí)間復(fù)雜性。1.4算法分析–算法漸近復(fù)雜性態(tài)?當(dāng)前第25頁\共有38頁\編于星期二\12點(diǎn)假設(shè)算法A的運(yùn)行時(shí)間表達(dá)式為T1(n)：

T1(n)=30n4+20n3+40n2+46n+100

T*1(n)≈n4（階）假設(shè)算法B的運(yùn)行時(shí)間表達(dá)式為T2(n)：

T2(n)=1000n3+50n2+78n+10

T*2(n)≈n3（階）1.4算法分析–算法漸近復(fù)雜性態(tài)示例當(dāng)前第26頁\共有38頁\編于星期二\12點(diǎn)1.4算法分析–幾類階的增長趨勢nLog2nnnlog2nn2n32nn!103.3103.3*101021031033.6*1061026.61026.6*1021041061.3*10309.3*10157103101031.0*1041061091.1*103014*102567增長趨勢：1個基本操作花1ns=10-6秒1年=31536000秒=3.15*107秒當(dāng)前第27頁\共有38頁\編于星期二\12點(diǎn)漸近意義下的記號：O、Ω、Θ漸近上界-O(bigo)漸近下界-Ω(bigω)漸近精確界-Θ(bigθ)o、ω和θ1.4算法分析–漸近復(fù)雜性記號當(dāng)前第28頁\共有38頁\編于星期二\12點(diǎn)漸近上界-O(bigo):設(shè)f(N)和g(N)是定義在正數(shù)集上的正函數(shù)，下同。定義：如果存在正的常數(shù)C和自然數(shù)N0，使得當(dāng)NN0時(shí)有f(N)Cg(N)，則稱函數(shù)f(N)當(dāng)N充分大時(shí)上有界，且g(N)是它的一個上界，記為f(N)=O(g(N))。即f(N)的階不高于g(N)的階。求T(n)=10n+4的漸近上界O：O(n)1.4算法分析–漸近上界當(dāng)前第29頁\共有38頁\編于星期二\12點(diǎn)根據(jù)O的定義，容易證明它有如下運(yùn)算規(guī)則：

(1)O(f)+O(g)=O(max(f,g))；

(2)O(f)+O(g)=O(f+g)；

(3)O(f)O(g)=O(fg)；

(4)如g(N)=O(f(N))，則(f)+O(g)=O(f)；

(5)O(cf(N))=O(f(N))，其中c是一個正的常數(shù)；

(6)f=O(f)。1.4算法分析–漸近上界O運(yùn)算規(guī)則當(dāng)前第30頁\共有38頁\編于星期二\12點(diǎn)常見的幾類算法復(fù)雜性：O(1)：常數(shù)階；O(log2n),O(nlog2n)：對數(shù)階；O(n),O(n2),O(n3),…,O(nm)：多項(xiàng)式階。多項(xiàng)式時(shí)間算法；O(2n),O(n!),O(nn)：指數(shù)階。指數(shù)時(shí)間算法。幾類復(fù)雜性之間的關(guān)系：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n)<O(n2)<O(n3)<…<O(nm)<O(2n)<O(n!)<O(nn)1.4算法分析–常見幾類復(fù)雜性當(dāng)前第31頁\共有38頁\編于星期二\12點(diǎn)Ω(bigomega)：如存在正的常數(shù)c和自然數(shù)n0，使得當(dāng)nn0時(shí)有f(n)cg(n)，則稱函數(shù)f(n)當(dāng)n充分大時(shí)下有界，且g(n)是它的一個下界，記為f(N)=Ω(g(n))。即f(n)的階不低于g(n)的階。Θ(bigtheta)：如存在正的常數(shù)c1,c2和自然數(shù)n0，使得當(dāng)nn0時(shí),有c1g(n)f(n)c2g(n)，則稱g(n)和f(n)同階。o、ω和θ與O、Ω和Θ。1.4算法分析–漸近復(fù)雜性記號2當(dāng)前第32頁\共有38頁\編于星期二\12點(diǎn)求T(n)=30n4+20n3+40n2+46n+100的漸近下界Ω：Ω(n4)求T(n)=20n2+8n+10的漸近精確界Θ：Θ(n2)求T(n)=amnm+am-1nm-1+…+a1n+a0的漸近上界O、下界Ω和精確界Θ：O(nm)、Ω(nm)和Θ(nm)1.4算法分析–漸近界示例當(dāng)前第33頁\共有38頁\編于星期二\12點(diǎn)1.4算法分析–漸近界示例當(dāng)前第34頁\共有38頁\編于星期