算法及其基礎(chǔ).ppt

《算法及其基礎(chǔ).ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第一章算法及其基礎(chǔ)1.1引子1.2算法的基本概念1.3算法設(shè)計(jì)的一般過程1.4算法分析1.5相關(guān)基礎(chǔ)本章的要點(diǎn)與難點(diǎn)要點(diǎn):理解算法的概念。程序與算法的區(qū)別和聯(lián)系；理解算法設(shè)計(jì)的一般過程；掌握用C++/JAVA語言以及偽代碼描述算法的方法；掌握算法的計(jì)算復(fù)雜性概念及分析。難點(diǎn):算法的計(jì)算復(fù)雜性（主要指時(shí)間復(fù)雜性）分析。1.1引子–排序問題排序問題描述：輸入：數(shù)字序列X=輸出：一個(gè)排列X‘=，數(shù)字序列X和排列X‘之間為滿射或一一映射（即元素一一對(duì)應(yīng)），并且有a‘1≤a‘2≤…≤a‘n（元素間非減

2、序）。例如：輸入：8,2,4,9,3,6輸出：2,3,4,6,8,9排序方法：冒泡、插入、歸并、二叉樹、桶排序等。穩(wěn)定的；選擇、Shell、堆、快速、組合排序等，不穩(wěn)定的。1.1引子–插入排序原理：通過構(gòu)建有序序列，對(duì)于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。偽代碼：INSERTION-SORT(A,n)//A[1..n]forj=2tondokey=A[j]i=j-1whilei>0andA[i]>keydoA[i+1]=A[i]i=i-1A[i+1]=key1.1引子–插入排序示例：1.1引子–插入排序證明–基于循環(huán)不變

3、式(LoopInvariant)：循環(huán)不變式：在每次循環(huán)迭代之前，子數(shù)組A[1..j-1]已包含了最初位于A[1..j-1]、但已排好序的各個(gè)元素。初始化：第一輪迭代之前（即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

4、]、且已排好序的各個(gè)元素。1.1引子–插入排序運(yùn)行時(shí)間分析：最壞情況：T(n)=O(n2)。，算術(shù)級(jí)數(shù)。已非升序排序；平均情況：T(n)=O(n2)。，算術(shù)級(jí)數(shù)；最好情況：T(n)=O(n)。，已升序排序。1.1引子–歸并排序原理：基于分而治之思想，遞歸地把待排序序列分解為若干子序列并進(jìn)行排序，再把已排序的子序列合并為整體有序序列，最終實(shí)現(xiàn)全序列的有序。偽代碼：MERGE-SORT(A,low,high)//A[1..n]iflow

5、A,mid+1,high)MERGE(A,low,mid,high)1.1引子–歸并排序示例MERGE-SORT：1.1引子–歸并排序(MERGE)MERGE：1.1引子–歸并排序證明：可以嘗試采用循環(huán)不變式自行證明，這里略。1.1引子–歸并排序運(yùn)行時(shí)間分析：算法(Algorithm)：對(duì)于計(jì)算機(jī)科學(xué)來說，算法指的是對(duì)特定問題求解步驟的一種描述，是若干條指令的有窮序列。算法的特性：輸入（0個(gè)或多個(gè)）、輸出（至少1個(gè)）、確定性（無歧義）、有限性、可行性。描述方式：自然語言、圖形、程序設(shè)計(jì)語言、偽代碼本書采用了面向?qū)ο蟪绦蛟O(shè)計(jì)語言C++，講授時(shí)采用

6、偽代碼。算法與程序的區(qū)別？1.2算法的基本概念–算法程序(Program)程序是算法用某種程序設(shè)計(jì)語言的具體實(shí)現(xiàn)；程序可以不滿足算法的性質(zhì)(4)。例如：操作系統(tǒng)是一個(gè)在無限循環(huán)中執(zhí)行的程序，因而其不是一個(gè)算法；操作系統(tǒng)的各種任務(wù)：可看成是單獨(dú)的問題，每一個(gè)問題由操作系統(tǒng)中的一個(gè)子程序通過特定的算法來實(shí)現(xiàn)。1.2算法的基本概念–程序會(huì)場安排問題、單源最短路徑、哈夫曼編碼、最小生成樹排序與查找、循環(huán)賽日程表最長公共子序列、矩陣連乘、凸多邊形最優(yōu)三角剖分、加工順序等N后、最大團(tuán)、圖的m著色0-1背包、TSP、布線問題等等1.2算法的基本概念–經(jīng)典問題

7、1.2算法的基本概念–拼圖游戲在n×n格的棋盤上放置彼此不受攻擊的n個(gè)皇后：按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子；n后問題等價(jià)于在n×n格的棋盤上放置n個(gè)皇后，任何2個(gè)皇后不放在同一行或同一列或同一斜線上。1234567812345678QQQQQQQQ1.2算法的基本概念–N后問題1.2算法的基本概念–0-1背包問題起點(diǎn)XXXXXXXXXXXXXXXXXXXX終點(diǎn)XXXXX1.2算法的基本概念–布線問題1.3算法設(shè)計(jì)的一般過程算法復(fù)雜性（亦稱算法復(fù)雜度）為算法運(yùn)行時(shí)所需計(jì)算機(jī)資源的度量：時(shí)間復(fù)雜性（影響因素

8、包括問題規(guī)模n、輸入序列I、算法本身A）：T(n,I,A)?T(n)空間復(fù)雜性（影響因素包括輸入輸出數(shù)據(jù)IO、輔助變量V、算法本身A）：S(IO,V,