算法及其基礎第1頁，課件共40頁，創作于2023年2月第一章算法及其基礎1.1引子1.2算法的基本概念1.3算法設計的一般過程1.4算法分析1.5相關基礎第2頁，課件共40頁，創作于2023年2月本章的要點與難點要點:

理解算法的概念。程序與算法的區別和聯系；理解算法設計的一般過程；掌握用C++/JAVA語言以及偽代碼描述算法的方法；掌握算法的計算復雜性概念及分析。難點:算法的計算復雜性（主要指時間復雜性）分析。第3頁，課件共40頁，創作于2023年2月1.1引子–排序問題排序問題描述：輸入：數字序列X=<a1,a2,…,an>輸出：一個排列X‘=<a‘1,a‘2,…,a‘n>，數字序列X和排列X‘之間為滿射或一一映射（即元素一一對應），并且有a‘1≤a‘2≤…≤a‘n（元素間非減序）。例如：輸入：8,2,4,9,3,6輸出：2,3,4,6,8,9排序方法：冒泡、插入、歸并、二叉樹、桶排序等。穩定的；選擇、Shell、堆、快速、組合排序等，不穩定的。第4頁，課件共40頁，創作于2023年2月1.1引子–插入排序原理：通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。偽代碼：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第5頁，課件共40頁，創作于2023年2月1.1引子–插入排序示例：第6頁，課件共40頁，創作于2023年2月1.1引子–插入排序證明–基于循環不變式(LoopInvariant)：循環不變式：在每次循環迭代之前，子數組A[1..j-1]已包含了最初位于A[1..j-1]、但已排好序的各個元素。初始化：第一輪迭代之前（即j=2），子數組A[1..j-1]（即A[1]）顯然保持了循環不變式；保持：假設第j次迭代之前循環不變式為真。該算法的第j次操作只是將A[j]與已有序的A[1..j-1]中的元素進行比較，找到合適位置并插入。j+1次迭代之前，很顯然A[1..(j+1)-1]也保持了循環不變式；終止：j=n+1時，顯然A[1..(n+1)-1]（即A[1..n]）已包含了最初位于A[1..n]、且已排好序的各個元素。第7頁，課件共40頁，創作于2023年2月1.1引子–插入排序運行時間分析：最壞情況：T(n)=O(n2)。，算術級數。已非升序排序；平均情況：T(n)=O(n2)。

，算術級數；最好情況：T(n)=O(n)。，已升序排序。第8頁，課件共40頁，創作于2023年2月1.1引子–歸并排序原理：基于分而治之思想，遞歸地把待排序序列分解為若干子序列并進行排序，再把已排序的子序列合并為整體有序序列，最終實現全序列的有序。偽代碼：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)第9頁，課件共40頁，創作于2023年2月1.1引子–歸并排序示例MERGE-SORT：第10頁，課件共40頁，創作于2023年2月1.1引子–歸并排序(MERGE)MERGE：第11頁，課件共40頁，創作于2023年2月1.1引子–歸并排序證明：可以嘗試采用循環不變式自行證明，這里略。第12頁，課件共40頁，創作于2023年2月1.1引子–歸并排序運行時間分析：第13頁，課件共40頁，創作于2023年2月算法(Algorithm)：對于計算機科學來說，算法指的是對特定問題求解步驟的一種描述，是若干條指令的有窮序列。

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

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

就稱T*(n)為算法的漸近性態或漸近時間復雜性。1.4算法分析–算法漸近復雜性態?第25頁，課件共40頁，創作于2023年2月假設算法A的運行時間表達式為T1(n)：

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

T*1(n)≈n4（階）假設算法B的運行時間表達式為T2(n)：

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

T*2(n)≈n3（階）1.4算法分析–算法漸近復雜性態示例第26頁，課件共40頁，創作于2023年2月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秒第27頁，課件共40頁，創作于2023年2月漸近意義下的記號：O、Ω、Θ漸近上界-O(bigo)漸近下界-Ω(bigω)漸近精確界-Θ(bigθ)o、ω和θ1.4算法分析–漸近復雜性記號第28頁，課件共40頁，創作于2023年2月漸近上界-O(bigo):設f(N)和g(N)是定義在正數集上的正函數，下同。定義：如果存在正的常數C和自然數N0，使得當NN0時有f(N)Cg(N)，則稱函數f(N)當N充分大時上有界，且g(N)是它的一個上界，記為f(N)=O(g(N))。即f(N)的階不高于g(N)的階。求T(n)=10n+4的漸近上界O：O(n)1.4算法分析–漸近上界第29頁，課件共40頁，創作于2023年2月根據O的定義，容易證明它有如下運算規則：

(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是一個正的常數；

(6)f=O(f)。1.4算法分析–漸近上界O運算規則第30頁，課件共40頁，創作于2023年2月常見的幾類算法復雜性：O(1)：常數階；O(log2n),O(nlog2n)：對數階；O(n),O(n2),O(n3),…,O(nm)：多項式階。多項式時間算法；O(2n),O(n!),O(nn)：指數階。指數時間算法。幾類復雜性之間的關系：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n)<O(n2)<O(n3)<…<O(nm)<O(2n)<O(n!)<O(nn)1.4算法分析–常見幾類復雜性第31頁，課件共40頁，創作于2023年2月Ω(bigomega)：如存在正的常數c和自然數n0，使得當nn0時有f(n)cg(n)，則稱函數f(n)當n充分大時下有界，且g(n)是它的一個下界，記為f(N)=Ω(g(n))。即f(n)的階不低于g(n)的階。Θ(bigtheta)：如存在正的常數c1,c2和自然數n0，使得當nn0時,有c1g(n)f(n)c2g(n)，則稱g(n)和f(n)同階。o、ω和θ與O、Ω和Θ。1.4算法分析–漸近復雜性記號2第32頁，課件共40頁，創作于2023年2月求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算法分析–漸近界示例第33頁，課件共40頁，創作于2023年2月1.4算法分析–漸近界示例第34頁，課件共40頁，創作于2023年2月非遞歸算法：順序語句：各語句計算時間相加；選擇語句：條件判定語句以及各分支中語句計算時間的較大者；循環語句：循環體內計算時間*循環次數，還需考慮循環判定條件；對于嵌套循環：循環體內計算時間*所有循環次數。1.4