廈門理工學(xué)院算法期末復(fù)習(xí).pdf

算法分析不設(shè)計 期末復(fù)習(xí) 陳 思 第一章 算法引論 算法不程序 表達(dá)算法的抽象機(jī)制 描述算法 算法時間復(fù)雜性分析 算法不程序 輸入 輸出 確定性 有限性 輸入 輸出 確定性 有限性 丌具有該特征 算法程序 算法復(fù)雜性分析 時間復(fù)雜性 空間復(fù)雜性 問題規(guī)模 具體輸入數(shù)據(jù) 算法設(shè)計 影響因素 時間復(fù)雜度 下界 上界 O 同階 時間的復(fù)雜性就是程序執(zhí)行的時間總和 算法按計算時間分類 多項(xiàng)式時間算法 定義 漸近時間復(fù)雜度由多項(xiàng)式時間限界的算法 特點(diǎn) 計算機(jī)的計算速度的乘法增長帶來的是求解問 題的規(guī)模的乘法增長 實(shí)例 常見的多項(xiàng)式時間算法漸近復(fù)雜度 O 1 O logn O n O nlogn O n2 O n3 指數(shù)時間算法 定義 漸近時間復(fù)雜度為指數(shù)函數(shù)限界的算法 特點(diǎn) 計算機(jī)的計算速度的乘法增長只帶來求解問 題規(guī)模的加法增長 實(shí)例 最常見的指數(shù)時間算法的漸近時間復(fù)雜度 O 2n O n O nn 第二章 遞歸不分治策略 遞歸 分治法 二分搜索技術(shù) 合并排序 快速排序 遞歸的概念遞歸的概念 遞歸函數(shù)遞歸函數(shù) 直接直接調(diào)用自己調(diào)用自己或通過另一函數(shù)或通過另一函數(shù)間接間接調(diào)用調(diào)用 自己自己的函數(shù)的函數(shù) 用遞歸求解問題的特點(diǎn)用遞歸求解問題的特點(diǎn) 1 存在遞歸的終止條件存在遞歸的終止條件 2 存在導(dǎo)致問題求解的遞歸方式存在導(dǎo)致問題求解的遞歸方式 ABC n n較大時較大時 怎么辦 怎么辦 3個圓盤的移動過程演示個圓盤的移動過程演示 A C n個圓盤需要個圓盤需要2n 1次移動次移動 n 64n 64時時 需要需要264 1 次移動 即次移動 即 1844億億次移動 億億次移動 若每次移動需用若每次移動需用1 1微秒微秒 則總共需要則總共需要 6060萬年時間 萬年時間 3個圓盤一共需要7次移動 A C A B C B A C B A B C A C HanoiHanoi問題問題 排列問題 有n個元素 把它們編號為1 2 n 用一個數(shù) 組A 來存放所生成的排列 然后輸出它們 假定開始時n 個元素依次存放在數(shù)組A中 為了生成這n個元素的所有 排列 可以采取下面的步驟 1 第一個元素為1 即排列的第一個元素為1 生 成后面n 1個元素的全排列 2 第一個元素和第二個元素互換 使排列的第一 個元素為2 生成后面n 1個元素的全排列 3 如此繼續(xù) 最后第一個元素和第n個元素互換 使排列的第一個元素為n 生成后面n 1個元素的全排列 在上面的第一步 為生成后面n 1個元素的排列 繼 續(xù)采取下面的步驟 1 第二個元素為2 即排列的第二個元素為2 生 成后面n 2個元素的排列 2 第二個元素和第三個元素互換 使排列的第二 個元素為3 生成后面n 2個元素的排列 3 如此繼續(xù) 最后第二個元素和第n個元素互換 使排列的第二個元素為n 生成后面n 2個元素的排列 這種步驟一直繼續(xù) 當(dāng)排列的前n 2個元素已確定后 為生成后面2個元素的排列 可以 1 第n 1個元素為n 1 即排列的第n 1個元素為n 1 生成后面1個元素的排列 此時n個元素已構(gòu)成一個排列 2 第n 1個元素和第n個元素互換 使排列的第n 1個元素為n 生成后面1個元素的排列 此時n個元素已構(gòu) 成一個排列 全排列算法全排列算法 void perm int list int k int m 產(chǎn)生list k m 的所有排列 其中l(wèi)ist 0 k 1 是前綴 后綴是list k m 調(diào)用perm list 0 n 1 則產(chǎn)生list 0 n 1 的全排列 if k m for i 0 i m i printf d list i 輸出list的一個排列 printf n else for i k i m i swap list k list i 交換list k 和list i perm list k 1 m 產(chǎn)生list k 1 m 的全排列 swap list k list i 交換list k 和list i 使list復(fù)原 分治法 適用條件 分治法所能解決的問題一般具有以下幾個特征 該問題的規(guī)?？s小到一定的程度就可以容易地解決 該問題可以分解為若干個規(guī)模較小的相同問題 即該問題具有最優(yōu)子 結(jié)構(gòu)性質(zhì) 利用該問題分解出的子問題的解可以合并為該問題的解 該問題所分解出的各個子問題是相互獨(dú)立的 即子問題之間丌包含公 共的子問題 分治法 基本步驟 divide and conquer P if P n0 adhoc P 解決小規(guī)模的問題 divide P into smaller subinstances P1 P2 Pk 分解問題 for i 1 i k i yi divide and conquer Pi 遞歸的解各子問題 return merge y1 yk 將各子問題的解合并為原問題的解 分治法 時間復(fù)雜性 通過迭代求解 log1 log 0 n m n jj m j T nkk f n m 二分搜索 public static int binarySearch int a int x int n 在 a 0 a 1 a n 1 中搜索 x找到x時返回其在數(shù)組中的位置 否則返回 1 int left 0 int right n 1 while left a middle left middle 1 else right middle 1 return 1 未找到x 給定已按升序排好序的n個元素a 0 n 1 現(xiàn)要在這n個元素中找出一特定元素x int binarySearch int a int num int left int right if left right return 1 未找到元素 int middle left right 2 if a middle num return middle else if a middle num return binarySearch a num left middle 1 else if a middle num return binarySearch a num middle 1 right 遞歸 注意遞歸凼數(shù)的參數(shù)順序 迭代 時間復(fù)雜度 合并排序 public static void mergeSort Comparable a int left int right if left right 至少有2個元素 int i left right 2 取中點(diǎn) mergeSort a left i mergeSort a i 1 right merge a b left i right 合并到數(shù)組b copy a b left right 復(fù)制回數(shù)組a 基本思想 將待排序元素分成大小大致相同的2個子集合 分別對2個子集合迚行排 序 最終將排好序的子集合合并成為所要求的排好序的集合 復(fù)雜度分析 T n O nlogn 漸進(jìn)意義下的最優(yōu)算法 快速排序 1 從數(shù)列中取出一個數(shù)作為中軸數(shù) 2 將比這個數(shù)大的數(shù)放到它的右邊 小于或等于它的數(shù)放到 它的左邊 3 再對左右區(qū)間重復(fù)第三步 直到各區(qū)間只有一個數(shù) 快速排序 private static void qSort int p int r if p 0 return m i j if i j return 0 int u lookupChain i 1 j p i 1 p i p j s i j i for int k i 1 k j k int t lookupChain i k lookupChain k 1 j p i 1 p k p j if t u u t s i j k m i j u return u 矩陣連乘 給定n個矩陣 A1 A2 An 其中Ai不Ai 1是可乘的 確 定一種連乘的順序 使得矩陣連乘的計算量為最小 設(shè)A和B分別是p q和q r的矩陣 則乘積C AB為p r的矩陣 計算量為pqr次數(shù)乘 但是對于多于2個以上的矩陣連乘 連乘的順序卻非常重要 因?yàn)樨⑼捻樞虻目傆嬎懔繉袕勾蟮牟顒e 矩陣連乘 最優(yōu)子結(jié)構(gòu) 將AiAi 1 Aj的矩陣連乘問題記為A i j 設(shè)A 1 n 的一個最優(yōu)解是在Ak和Ak 1處斷開的 即A 1 n A 1 k A k 1 n 則A 1 k 和A k 1 n 也分別是其最 優(yōu)解 否則 若有A 1 k 的一個計算次序的計算量更少的話 則用 此計算次序替換原來的次序 則得到A 1 n 一個更少計算量 矛盾 同理A k 1 n 也是最優(yōu)解 矩陣連乘 遞歸關(guān)系式 令m i j 1 i j n 為計算A i j 的最少數(shù)乘次數(shù) 則原問題為 m 1 n 當(dāng)i j時 A i j 為單一矩陣 m i j 0 當(dāng)i j時 利用最優(yōu)子結(jié)構(gòu)性質(zhì)有 m i j min m i k m k 1 j pi 1pkpj i k j 其中矩陣Ai 1 i n 的維數(shù)為pi 1 pi 矩陣連乘算法的數(shù)據(jù)結(jié)構(gòu) 形參表中應(yīng)有n和P n 1 算法需要兩個二維數(shù)組 二維矩陣m n n 其每個元素m i j 1 i j n 為A i j 的最少數(shù)乘次數(shù) 二維矩陣s n n 其元素s i j 1 i j n 為計算A i j 的 斷點(diǎn)位置 只需數(shù)組P n 1 就可存放各矩陣的行列數(shù) 注意 因?yàn)檫@注意 因?yàn)檫@n個矩陣可乘 故后一個矩陣的行數(shù)就是個矩陣可乘 故后一個矩陣的行數(shù)就是 一個矩陣的列數(shù) 一個矩陣的列數(shù) P 0 為為A1的行數(shù)的行數(shù) P 1 為為A2的行數(shù)的行數(shù) 也是也是A1的列數(shù)的列數(shù) 其余類推 最后的其余類推 最后的P n 是是An的列數(shù)的列數(shù) void matrixChain int p int m int s for int i 1 i n i m i i 0 int n p length 1 for int r 2 r n r for int i 1 i n r 1 i int j i r 1 m i j m i 1 j p i 1 p i p j k i s i j i for int k i 1 k j k int t m i k m k 1 j p i 1 p k p j if t m i j m i j t s i j k 最長公共子序列 公共子序列定義 給定2個序列X和Y 當(dāng)另一序列Z既是X的子序列又是Y的子序列時 稱Z是序列 X和Y的公共子序列 最長公共子序列 公共子序列中長度最長的子序列 最長公共子序列問題 給定2個序列X x1 x2 xm 和Y y1 y2 yn 找出X和Y的最長公共子序 列 最長公共子序列 遞歸關(guān)系 由最長公共子序列問題的最優(yōu)子結(jié)構(gòu)性質(zhì)建立子問題最優(yōu)值的遞歸關(guān) 系 用c i j 記彔序列和的最長公共子序列的長度 其中 Xi x1 x2 xi Yj y1 y2 yj 當(dāng)i 0或j 0時 空序列是Xi和Yj 的最長公共子序列 故此時C i j 0 其它情況下 由最優(yōu)子結(jié)構(gòu)性 質(zhì)可建立遞歸關(guān)系如下 最長公共子序列 遞歸算法 int lcsLenght String x String y int m x length n y length return lcs x y m n int lcs String x String y int i int j if i 0 j 0 return 0 if x i y i return lcs x y i 1 j 1 1 return max lcs x y i 1 j lcs x y i j 1 0 1背包問題 給定n種物品和一背包 物品i的重量是wi 其價值為vi 背包的容量為C 問應(yīng)如何選擇裝入背包中的物品 使得裝入背包中物品的總價值最大 對每種物品i裝入背包或丌裝入背包 丌能將物品i裝入背包多次 也丌能 只裝入部分的物品i 0 1背包問題 遞歸關(guān)系 m i j 是背包容量為j 可選擇物品為i i 1 n時0 1背 包問題的最優(yōu)值 第i個物品不裝入背包 第i個物品裝入背包 第i個物品無法裝入背包 0 1背包問題 動態(tài)規(guī)劃 void knapsack int v int w int c int m int n v length 1 int jMax min w n 1 c 背包剩余容量 for int j 0 j jMax j 背包裝丌下w n 的情況 m n j 0 for int j w n j1 i jMax min w i 1 c for int j 0 j jMax j 背包裝丌下w i 的情況 m i j m i 1 j 沒產(chǎn)生仸何效益 for int j w i j w 1 如果背包裝得下w 1 m 1 c max m 1 c m 2 c w 1 v 1 構(gòu)造物品選擇狀態(tài)序列 void traceback int m int w int c int x 求最優(yōu)解xi int n w length 1 for int i 1 i0 1 0 0 1背包問題 012345678910 w1 2 v1 6 1 w2 2 v2 3 2 w3 6 v3 5 3 w4 5 v4 4 4 w5 4 v5 6 5 0 問題實(shí)例 有5個物品 其重量分別是 2 2 6 5 4 價值分別為 6 3 5 4 6 背包的容量為10 0 00 00 00 06 66 66 66 66 66 66 6 m 5 4 m 5 4 6 6 0 1背包問題 012345678910 w1 2 v1 6 1 w2 2 v2 3 2 w3 6 v3 5 3 w4 5 v4 4 4 w5 4 v5 6 5 0 問題實(shí)例 有5個物品 其重量分別是 2 2 6 5 4 價值分別為 6 3 5 4 6 背包的容量為10 0 00 00 00 06 66 66661010 0 00 00 00 06 66 66 66 66 66 66 6 v 4 容量為5 5的背包 考慮是否裝入物 品4 4 0 1背包問題 012345678910 w1 2 v1 6 1 w2 2 v2 3 2 w3 6 v3 5 3 w4 5 v4 4 4 w5 4 v5 6 5 0 問題實(shí)例 有5個物品 其重量分別是 2 2 6 5 4 價值分別為 6 3 5 4 6 背包的容量為10 0 00 06 66 69 99 912121212151515151515 0 00 03 33 36 66 69 99 99 910101111 0 00 00 00 06 66 66 66 66 610101111 0 00 00 00 06 66 66 66 66 610101010 0 00 00 00 06 66 66 66 66 66 66 6 0 1背包問題 統(tǒng)計結(jié)果 問題實(shí)例 有5個物品 其重量分別是 2 2 6 5 4 價值分別為 6 3 5 4 6 背包的容量為10 第四章 貪心算法 貪心算法的基本要素 活動安排問題 單源最短路徑 最小生成樹 貪心算法 基本思想 找出整體當(dāng)中每個小的局部的最優(yōu)解 并且將所有的這些局找出整體當(dāng)中每個小的局部的最優(yōu)解 并且將所有的這些局 部最優(yōu)解合起來形成整體上的一個解部最優(yōu)解合起來形成整體上的一個解 貪心算法并不從整體最優(yōu)考慮 它所作出的選擇只是在某種貪心算法并不從整體最優(yōu)考慮 它所作出的選擇只是在某種 意義上的局部最優(yōu)選擇 意義上的局部最優(yōu)選擇 所以不能保證最優(yōu)解所以不能保證最優(yōu)解 0 0 1 1背包問題 不能用貪心算法 背包問題 可以用貪心算法 背包問題 不能用貪心算法 背包問題 可以用貪心算法 貪心算法 基本要素 貪心選擇性質(zhì) 所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇 即 貪心選擇來達(dá)到 最優(yōu)子結(jié)構(gòu)性質(zhì) 當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時 稱此問題具 有最優(yōu)子結(jié)構(gòu)性質(zhì) 貪心算法 一般框架 GreedyAlgorithm parameters 初始化 重復(fù)執(zhí)行以下的操作 選擇當(dāng)前可以選擇的 相容 最優(yōu)解 將所選擇的當(dāng)前解加入到問題解中 直至滿足問題求解的結(jié)束條件 活動安排問題 活動安排問題就是要在所給的活動集合中選出最大的相容活 動子集合 活動相容的定義 每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束 時間fi 且si fi 如果選擇了活動i 則它在半開時間區(qū)間 si fi 內(nèi)占用資源 若區(qū)間 si fi 不區(qū)間 sj fj 丌相交 則稱活動i不 活動j是相容的 也就是說 當(dāng)si fj或sj fi時 活動i不活動j相 容 活動安排問題 活動安排問題 public static int greedySelector int s int f boolean a int n s length 1 a 1 true int j 1 int count 1 for int i 2 i f j a i true j i count else a i false return count 單源最短路徑 給定帶權(quán)有向圖G V E 其中每條邊的權(quán)是非負(fù)實(shí)數(shù) 另 外 還給定V中的一個頂點(diǎn) 稱為源 現(xiàn)在要計算從源到所有 其它各頂點(diǎn)的最短路長度 這里路的長度是指路上各邊權(quán)之 和 這個問題通常稱為單源最短路徑問題 單源最短路徑 DIJKSTRADIJKSTRA算法算法 基本思想基本思想是 設(shè)置是 設(shè)置頂點(diǎn)集合頂點(diǎn)集合S S并不斷地做并不斷地做貪心選擇貪心選擇來擴(kuò)充這個集合 來擴(kuò)充這個集合 一個頂點(diǎn)屬于集合一個頂點(diǎn)屬于集合S S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長度已知 當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長度已知 初始時 初始時 S S中僅含有源 中僅含有源 設(shè)設(shè)u u是是G G的某一個頂點(diǎn) 把的某一個頂點(diǎn) 把從源到從源到u u且中間只經(jīng)過且中間只經(jīng)過S S中頂點(diǎn)的路中頂點(diǎn)的路稱稱 為為從源到從源到u u的的特殊路徑特殊路徑 并用 并用數(shù)組數(shù)組distdist記錄當(dāng)前每個頂點(diǎn)所對應(yīng)的記錄當(dāng)前每個頂點(diǎn)所對應(yīng)的最最 短特殊路徑長度短特殊路徑長度 DijkstraDijkstra算法每次算法每次從從V V S S中取出具有最短特殊路徑長度的頂點(diǎn)中取出具有最短特殊路徑長度的頂點(diǎn)u u 將將u u添加到添加到S S中 同時對數(shù)組中 同時對數(shù)組distdist作必要的修改 一旦作必要的修改 一旦S S包含了所有包含了所有V V 中頂點(diǎn) 中頂點(diǎn) distdist就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長度 就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長度 DijkstraDijkstra算法算法 迭代迭代S Su udist 2 dist 2 dist 3 dist 3 dist 4 dist 4 dist 5 dist 5 初始初始 1 1 1010maxintmaxint3030100100 1 1 1 2 1 2 2 2101060603030100100 2 2 1 2 4 1 2 4 4 41010505030309090 3 3 1 2 4 3 1 2 4 3 3 31010505030306060 4 4 1 2 4 3 5 1 2 4 3 5 5 51010505030306060 DijkstraDijkstra算法算法 void dijkstra int v float a float dist int prev int n dist length 1 boolean s new boolean n 1 if vn return for i 1 i n i dist i a v i s i false if dist i MAX VALUE prev i 0 else prev i v dist v 0 s v true for i 1 i n i u v temp MAX VALUE for j 1 j n j if s j temp dist j s u true for j 1 j n j if s j prev j u O N2 最小生成樹 設(shè)G V E 是無向連通帶權(quán)圖 即一個網(wǎng)絡(luò) 如果G的一個子圖G 是一棵包含G的所有頂點(diǎn)的樹 則稱G 為G 的生成樹 生成樹各邊權(quán)的總和稱為其耗費(fèi) 在G的所有生成樹中 耗費(fèi)最小的生成樹稱為G的最小 優(yōu) 生成樹 Prim算法 和 Kruskal算法 PRIM算法 在保證連通的前提下依次選出權(quán)重較小的n 1條邊 在實(shí)現(xiàn)中 體現(xiàn)為n個頂點(diǎn)的選擇 1 2 3 4 56 1 65 5 5 36 6 24 1 3 1 2 3 4 56 1 65 5 5 36 6 24 1 3 6 1 2 3 4 56 1 65 5 5 36 6 24 1 3 6 4 1 2 3 4 56 1 65 5 5 36 6 24 1 3 6 42 1 2 3 4 56 1 65 5 5 36 6 24 1 3 6 42 5 PRIM算法 void prim int n float c s 1 true for int i 2 i n i lowcost i c 1 i closet i 1 s i false for int i 1 i n i float min Float MAX VALUE int j 1 for int k 2 k n k if lowcost k min j k s j true for int k 2 k n k if c j k lowcost k closest k j O N2 KRUSKAL算法 在保證無回路的前提下依次選擇權(quán)重較小的n 1條邊 1 2 3 4 56 1 65 5 5 36 6 2 4 131 462 253 364 145 235 345 126 356 566 1 2 3 4 56 1 2 3 4 56 1 2 3 4 56 1 2 3 4 56 1 2 3 4 56 KRUSKAL算法的實(shí)現(xiàn) Kruskal int n e Sort e w initialize n k 1 j 1 while k n a Find e j u b Find e j v if a b t k j Union a b j O eloge 第五章 回溯法 回溯法的算法框架 裝載問題 N皇后問題 圖的M著色問題 回溯法 回溯法的基本做法是搜索 是一種組織得井井有條的 能避 免丌必要