算法分析與設(shè)計多媒體課件

1、算法設(shè)計與分析算法設(shè)計與分析Algorithm Design and Analysis湖南商學院計算機與電子工程學院2009.52022-4-291算法設(shè)計與分析目錄qChapter1 Chapter1 緒論緒論qChapter2 Chapter2 算法效率分析基礎(chǔ)算法效率分析基礎(chǔ) qChapter3 Chapter3 分治法分治法 qChapter4 Chapter4 減治法減治法qChapter5 Chapter5 變治法變治法qChapter6 Chapter6 時空權(quán)衡時空權(quán)衡qChapter7 Chapter7 動態(tài)規(guī)劃動態(tài)規(guī)劃qChapter8 Chapter8 貪心法貪心法qCh

2、apter9 Chapter9 回溯與分枝限界回溯與分枝限界附：算法設(shè)計與分析實例動畫集成 Chapter1 緒論 Introduction2022-4-293算法設(shè)計與分析緒論q什么是算法q算法的實例q算法研究的基本問題q為什么要學習算法q已有的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)返回總目錄2022-4-294算法設(shè)計與分析什么是算法 算法是為了解決某一問題而設(shè)計的無疑義的指令序列，對于合法的輸入，能在有限的時間內(nèi)得出所需要的輸出。problemalgorithmcomputerinputoutput2022-4-295算法設(shè)計與分析算法滿足下列性質(zhì)n輸 入：有零個或多個外部量作為算法的輸入。 n輸 出：算法產(chǎn)生至

3、少一個量作為輸出。 n確定性：組成算法的每條指令清晰、無歧義。 n有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時間也有限。2022-4-296算法設(shè)計與分析算法的實例q排序q查找q最短路徑q最小生成樹q旅行商問題q背包問題q皇后問題q漢諾塔2022-4-297算法設(shè)計與分析算法研究的基本問題q如何設(shè)計算法q如何描述算法q證明算法的正確性q常用數(shù)學歸納法q算法效率q理論分析q實證分析q算法優(yōu)化2022-4-298算法設(shè)計與分析為什么要學習算法q理論學習上的重要性q計科專業(yè)的核心課程q計科專業(yè)的基礎(chǔ)課程q實踐上的重要性2022-4-299算法設(shè)計與分析已有的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)q典型的問題類型q排

4、序q查找q字符串處理q圖q組合問題q幾何問題q數(shù)值問題2022-4-2910算法設(shè)計與分析已有的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)q數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)q表n數(shù)組n鏈表n字符串q棧和隊列q圖q樹q集合和字典2022-4-2911算法設(shè)計與分析思考q帶鎖的門走廊上n個帶鎖的門，從1到n一次編號，最初都關(guān)著，我們從門前經(jīng)過n次，每次都從1號門開始，在第i次經(jīng)過時，我們改變i的倍數(shù)的門所狀態(tài)，這樣，最后一次經(jīng)過時，那些門開著，那些門關(guān)著？q有四個人過橋，他們都在橋的一端，17分鐘讓他們?nèi)客ㄟ^，必須攜帶手電筒，必須步行攜帶，每個人速度不同，甲過橋一分鐘，乙過橋2分鐘，丙過橋5分鐘，丁要10分鐘，2個人一起走需要的時間是較慢的人的

5、時間，他們要如何走才能順利完成？2022-4-2912算法設(shè)計與分析本章結(jié)束，返回總目錄 Chapter2 算法效率分析基礎(chǔ) Foundation of Algorithm Analysis2022-4-2914算法設(shè)計與分析算法效率分析基礎(chǔ)q研究的主要問題q方法q時間效率的理論分析q時間效率的實證分析q最好、最壞與平均情況q增長速度q非遞歸與遞歸分析過程返回總目錄2022-4-2915算法設(shè)計與分析研究的主要問題q算法的正確性q時間效率q空間效率q最優(yōu)性2022-4-2916算法設(shè)計與分析方法q理論分析q實證分析2022-4-2917算法設(shè)計與分析2.1時間效率的理論分析q輸入規(guī)模q 基本運

6、算 為什么要用基本運算？如何找基本運算？運行時間基本運算的執(zhí)行時間基本運算的執(zhí)行次數(shù)輸入規(guī)模 T(n) copC(n)2022-4-2918算法設(shè)計與分析輸入規(guī)模與基本操作舉例基本運算輸入規(guī)模的度量問題對節(jié)點或?qū)叺脑L問節(jié)點數(shù)或者邊數(shù)典型的圖問題除法n的大?。ń?jīng)常轉(zhuǎn)化為二進制表示，即為二進制的位數(shù)）對于給定的數(shù)n，判斷是否為素數(shù)兩個數(shù)相乘矩陣的維度或者元素的個數(shù)兩個矩陣相乘關(guān)鍵字比較列表節(jié)點數(shù)目，例如 n在長度為n的列表中按關(guān)鍵字查找2022-4-2919算法設(shè)計與分析對時間效率的實證分析q選擇特別的或者典型的輸入q統(tǒng)計q實際運行時間 (e.g., milliseconds)q統(tǒng)計基本操作執(zhí)行

7、的次數(shù)q對統(tǒng)計數(shù)據(jù)進行分析2022-4-2920算法設(shè)計與分析最好、最壞、平均情況q很多算法的效率都取決于輸入的組織q最壞情況: Cworst(n) 對于規(guī)模為n的輸入，最大的消耗q最好情況: Cbest(n) 對于規(guī)模為n的輸入，最小的消耗q平均情況: Cavg(n)對于規(guī)模為n的輸入，“平均”的消耗q基本操作執(zhí)行的次數(shù)體現(xiàn)在典型輸入中q不是最好最壞情況的平均q將規(guī)模n的實例劃分為幾種類型，同種實例所需要的基本操作執(zhí)行次數(shù)一樣，然后我們得到或者假設(shè)各種輸入的概率分布，以推導出我們的平均次數(shù)2022-4-2921算法設(shè)計與分析例：順序查找q最壞情況：nq最好情況：1q平均情況：(1+n)p/2

8、+n(1-p)/在一個指定的數(shù)組中順序查找指定元素/輸入：A0.n-1,k/輸出：指定查找元素在數(shù)組中的下標，沒有返回-12022-4-2922算法設(shè)計與分析思考q對于下面每種算法，1.指出輸入規(guī)模的合理度量，2.它的基本操作，對相同規(guī)模的輸入來說，3.基本操作的執(zhí)行次數(shù)是否有所不同？ a、計算n個數(shù)的和 b、計算n！ c、找出包含n個數(shù)字的列表的最大元素 c、兩個十進制正整數(shù)相乘的筆算算法 d、歐幾里得法求公約數(shù)2022-4-2923算法設(shè)計與分析q選擇手套一個抽屜里有22只手套，5雙紅色的，4雙黃色的，2雙綠色的，黑暗中挑選，最優(yōu)情況下就最少選幾只能找到一對匹配的手套？最壞情況下呢？q丟失

9、的襪子 假設(shè)洗了5雙不同的襪子后，發(fā)現(xiàn)兩只找不到了，當然希望留下數(shù)量最多的完整的襪子，在最好的情況下，你會留下4雙襪子，最壞情況下只有3雙，假設(shè)10只襪子每只丟失的概率相同，請找出最好與最壞的發(fā)生概率，平均情況下能指望有幾雙？2022-4-2924算法設(shè)計與分析增長次數(shù) q最重要的: 考慮n時，效率的乘積增長速度q例如：q當計算機的速度增加兩倍時，算法運行的速度會有多快q當在兩倍的輸入規(guī)模下解決某問題時，時間會增加多少 T(n) copC(n)2022-4-2925算法設(shè)計與分析n時的重要增長值比較一下logn與n2的區(qū)別2022-4-2926算法設(shè)計與分析分析框架概要q算法的效率用輸入規(guī)模函

10、數(shù)進行度量q基本操作的執(zhí)行次數(shù)q輸入規(guī)模相同情況下，有時候需要區(qū)分最好、最差和平均效率q算法輸入規(guī)模趨向無窮大時，它的運行時間函數(shù)的增長次數(shù)2022-4-2927算法設(shè)計與分析2.2增長率漸進表示q我們關(guān)心的是算法的基本操作次數(shù)的增長次數(shù)，并把它作為算法效率分析的主要指標，為了進行比較歸類，引入下列3個符號：qO(g(n): 增長不會超過g(n) 的一類函數(shù)f(n)q(g(n):增長率與g(n)相同的一類函數(shù)f(n)q(g(n):增長至少與g(n)相同的一類函數(shù)f(n)2022-4-2928算法設(shè)計與分析Big-oh成立的條件是對于足夠大的nn0，存在大于0的常數(shù)c，使得以上圖形滿足,后面符號

11、的兩個條件相同P41例2022-4-2929算法設(shè)計與分析Big-omega2022-4-2930算法設(shè)計與分析Big-theta2022-4-2931算法設(shè)計與分析)()1(212nnn證明2022-4-2932算法設(shè)計與分析漸進增長的相關(guān)屬性qf(n) O(f(n)qf(n) O(g(n) if g(n) (f(n)qIf f (n) O(g (n) and g(n) O(h(n) , then f(n) O(h(n)qIf f1(n) O(g1(n) and f2(n) O(g2(n) , then f1(n) + f2(n) O(maxg1(n), g2(n) 2022-4-2933算

12、法設(shè)計與分析使用極限比較增長次數(shù)qlim T(n)/g(n) = 0 order of growth of T(n) 0 order of growth of T(n) = order of growth of g(n) order of growth of T(n) order of growth of g(n) Examples: 10n vs. n2 n(n+1)/2 vs. n2 n2022-4-2934算法設(shè)計與分析基本的漸進效率分類：1常數(shù)log n對數(shù)n線性n log nn-log-nn2平方n3立方2n指數(shù)n!階乘2022-4-2935算法設(shè)計與分析qP46 1選擇合適的符號來

13、指出順序查找算法時間效率類型q最優(yōu)q最差q平均情況q作業(yè) 2、52022-4-2936算法設(shè)計與分析2.3非遞歸算法時間效率分析過程q使用變量n來描述輸入規(guī)模q定義算法的基本操作q在輸入規(guī)模為n的情況下，區(qū)分最壞、平均和最好情況q對基本操作執(zhí)行的次數(shù)求和q使用相關(guān)公式和規(guī)則對和進行化簡2022-4-2937算法設(shè)計與分析示例1：求最大元素2022-4-2938算法設(shè)計與分析示例2：元素的唯一性問題2022-4-2939算法設(shè)計與分析示例3：矩陣的乘法2022-4-2940算法設(shè)計與分析示例4.十進制數(shù)轉(zhuǎn)化成二進制數(shù)后的位數(shù) 2022-4-2941算法設(shè)計與分析q練習 p51 1 e、g 其余作

14、業(yè)2022-4-2942算法設(shè)計與分析2.4遞歸算法的時間效率分析過程q遞歸算法：q函數(shù)調(diào)用自身的情況稱為遞歸。q遞歸的條件：q子問題與原問題是同樣的問題，且更為簡單q不能無限制調(diào)用，必須有出口條件2022-4-2943算法設(shè)計與分析q確定一個變量來描述輸入規(guī)模q確定算法的基本操作q對于相同規(guī)模的不同輸入，在執(zhí)行時是否有不同的基本操作次數(shù)，如果有，那么最壞、平均和最好情況應(yīng)該分別考慮q建立與適當初始條件的遞歸聯(lián)系，表示基本操作的執(zhí)行次數(shù)q使用反向迭代方法和初始條件解出遞歸式，至少要建立遞歸解的增長率2022-4-2944算法設(shè)計與分析N!定義: n ! = 1 2 (n-1) n for n

15、1 and 0! = 1遞歸的定義 n!: F(n) = F(n-1) n for n1 and F(0) = 1問題規(guī)模？基本操作？運算時間的遞推式？初始條件？2022-4-2945算法設(shè)計與分析q實例2：漢諾塔問題q實例3：十進制正整數(shù)在二進制表示中的數(shù)字個數(shù) 遞歸方法 q練習p58頁（1） a b、c、d、e做作業(yè)qP64頁 習題2.5 （4）2022-4-2946算法設(shè)計與分析本章結(jié)束，返回總目錄Chapter3 分治法 Divid and Conquer2022-4-2948算法設(shè)計與分析分治法q分治法q通用分治遞推式q分治法實例返回總目錄2022-4-2949算法設(shè)計與分析分治法q

16、通用算法設(shè)計技術(shù)q將問題的實例劃分為同一個問題的幾個較小實例q對這些較小的實例求解q合并這些較小問題的解，已得到原始問題的解q分治算法很適合用遞歸來解決2022-4-2950算法設(shè)計與分析分治法子問題子問題2的規(guī)模是的規(guī)模是n/2子問題子問題1的規(guī)模是的規(guī)模是n/2子問題子問題1的解的解原始問題的解原始問題的解子問題子問題2的解的解原始問題規(guī)模是原始問題規(guī)模是n2022-4-2951算法設(shè)計與分析通用分治遞推式T(n) = aT(n/b) + f (n) 其中， f(n) (nd), d 0主定理: 當 a bd, T(n) (nlog b a ) 注意：對 O 和符號來說類似的結(jié)論也是成立的

17、。例如: T(n) = 4T(n/2) + n T(n) ? T(n) = 4T(n/2) + n2 T(n) ? T(n) = 4T(n/2) + n3 T(n) ?2022-4-2952算法設(shè)計與分析分治法實例q歸并排序和快速排序q二叉樹遍歷q二分查找q大整數(shù)乘法qStrassen矩陣乘法q凸包問題2022-4-2953算法設(shè)計與分析歸并排序q將數(shù)組A0.n-1 分成兩個相等數(shù)組，并分別用數(shù)組B和數(shù)組C備份q分別對B,C進行排序q按照如下方法合并B,C到數(shù)組A ：q重復如下步驟，直到數(shù)組中沒有元素為止 ：n比較兩個待合并數(shù)組的第一個元素n將較小的元素添加到一個新創(chuàng)建的數(shù)組中，被復制數(shù)組中下

18、標后移。q在未處理完的數(shù)組中，剩下的元素被復制到新創(chuàng)建數(shù)組的尾部。2022-4-2954算法設(shè)計與分析8 3 2 9 7 1 5 48 3 2 97 1 5 48 32 97 15 4832971543 82 91 74 52 3 8 91 4 5 71 2 3 4 5 7 8 92022-4-2955算法設(shè)計與分析兩個列表歸并成一個有序列表的算法2022-4-2956算法設(shè)計與分析歸并排序算法2022-4-2957算法設(shè)計與分析歸并排序效率分析q所有實例都有同一個效率: (n log n) q最壞情況下的鍵值比較次數(shù)十分接近于任何基于比較的排序算法在理論上所能達到的最少次數(shù). 當n=2k時

19、c(n)=nlog2n-n+1q空間需求: (n) q可以不用遞歸(自底而上）2022-4-2958算法設(shè)計與分析快速排序q選擇一個中軸 元素，我們這里選擇第一個元素q對數(shù)組進行排序，使得小于或等于中軸的元素位于子數(shù)組的第一部分，剩下的元素都大于或等于中軸元素的值。q將中軸子與第一個子數(shù)組中的元素進行交換-此時，中軸在最后的位置q對兩個子數(shù)組進行遞歸排序2022-4-2959算法設(shè)計與分析 0 1 2 3 4 5 6 7 5 3 1 4 8 2 9 7 5 3 1 9 8 2 4 7 3 1 9 8 2 4 7 5 3 1 4 8 2 9 7 5 3 1 4 2 8 9 7 5 3 1 4 2

20、 8 9 7 2 3 1 4 5 8 9 7ijl=0,r=7 5ijijijijjiS=4 2 3 1 4 ijl=0,r=3 2 3 1 4 ij 2 1 3 4 ij 2 1 3 4 ij 1 2 3 4 S=1 1 l=5,r=7 3 4 i j 3 4 ij 4 l=0,r=0l=2,r=3S=2l=2,r=1l=3,r=3 8 9 7ij 8 7 9ij 8 7 9ij 7 8 9l=5,r=5 7 9 l=7,r=7S=6快速排序操作的一個例子。(a)數(shù)組的變化，其中中軸用粗體表示；(b)快速排序的遞歸調(diào)用樹，調(diào)用的輸入值是子數(shù)組的邊界l和r，以及分區(qū)的分裂點位置s(a)(b)2

21、022-4-2960算法設(shè)計與分析快排效率分析q最好情況: 從中間拆分 (n log n) q最壞情況: 已經(jīng)是排好序的數(shù)組 (n2) q平均情況: 無序數(shù)組 (n log n)q對該算法的改進:q更好的選擇中軸: 三平均分區(qū)法 q當子數(shù)組足夠小時改用更簡單的排序方法q遞歸消去法n可將該算法的運行時間削減20%-25%q考慮用該種方法來對大文件（n10000) 來進行內(nèi)部排序2022-4-2961算法設(shè)計與分析二分查找對于有序數(shù)組的查找的一種高速算法 K vsA0 . . . Am . . . An-1q如果 K=Am, 停止查找; q否則當K Am 時，在 Am+1.n-1中查找。2022-

22、4-2962算法設(shè)計與分析二分查找效率分析q時間效率q最壞情況下遞推式： Cw (n) = 1 + Cw( n/2 ), Cw (1) = 1 q經(jīng)過調(diào)整后： Cw(n) = log2(n+1) 這是非常快的，例如：Cw(106) = 20q最適合用于查找已排序數(shù)組q限制：必須是一個排序數(shù)組（不是鏈接數(shù)組）q折半查找并不是分治法典型的特例2022-4-2963算法設(shè)計與分析二叉樹遍歷二叉樹時分治法的較好的結(jié)構(gòu)例1: 遍歷 (前序, 中序, 后序)Algorithm Inorder(T)if T Inorder(Tleft) print(root of T) Inorder(Tright) 效率

23、: (n) 2022-4-2964算法設(shè)計與分析二叉樹遍歷例 2: 計算二叉樹的高度 TTLR 2022-4-2965算法設(shè)計與分析大整數(shù)乘法兩位整數(shù)相乘可以用數(shù)組表示如：a1 a2 anb1 b2 bnA = 12345678901357986429B = 87654321284820912836(d10) d11d12 d1n(d20) d21d22 d2n(dn0) dn1dn2 dnn效率：O(n2)2022-4-2966算法設(shè)計與分析大整數(shù)乘法兩位數(shù)兩位數(shù)A = 2135 和和B = 4014可以這樣表示：可以這樣表示：將每個數(shù)字從中間一分為二將每個數(shù)字從中間一分為二它們的積可以用這

24、個公式計算：它們的積可以用這個公式計算：A B = A1 B110n + (A1 B2 + A2 B1) 10n/2 + A2 B2 A = (21102 + 35), B = (40 102 + 14) A B = (21 102 + 35) (40 102 + 14) = 21 40 104 + (21 14 + 35 40) 102 + 35 14效率效率： M(n) = 4M(n/2), M(1) = 1 M(n) = n2 2022-4-2967算法設(shè)計與分析大整數(shù)乘法(A1 B2 + A2 B1) = (A1 + A2 ) (B1 + B2 ) - A1 B1 - A2 B2A B

25、 = A1 B110n + (A1 B2 + A2 B1) 10n/2 + A2 B2可以這樣做減少乘法：A B = A1 B1 + (A1 B2 + A2 B1) + A2 B2因為上述中只有三個乘法所以乘法次數(shù)M(n)的遞推式是： 當n1時 M(n)=3M(n/2), M(1)=1 當n=2k時 M(2k)= 3M(2 k-1)=.=3k 因為：k=log2n M(n)=nlog23=n1.5852022-4-2968算法設(shè)計與分析大整數(shù)乘法 A = 21 35 B = 40 14 A1A2B1B2A B =21*35+（21*14+35*40）+35*14（21*14+35*40）=（2

26、1+35）*（40+24）- 21*35 - 35*14例如： 計算計算 2135 4014 2022-4-2969算法設(shè)計與分析A和B的乘積矩陣C中的元素Ci,j定義為: nkjkBkiAjiC1若依此定義來計算A和B的乘積矩陣C，則每計算C的一個元素Cij，需要做n次乘法和n-1次加法。因此，算出矩陣C的 個元素所需的計算時間為O(n3)u傳統(tǒng)方法：O(n3)2022-4-2970算法設(shè)計與分析使用與上例類似的技術(shù)，將矩陣A，B和C中每一矩陣都分塊成4個大小相等的子矩陣。由此可將方程C=AB重寫為：u傳統(tǒng)方法：O(n3)u分治法:222112112221121122211211BBBBAA

27、AACCCC由此可得：2112111111BABAC2212121112BABAC2122112121BABAC2222122122BABAC由此可見，單純采用分治法，沒有改進2022-4-2971算法設(shè)計與分析為了降低時間復雜度，必須減少乘法的次數(shù)。222112112221121122211211BBBBAAAACCCC)(2212111BBAM2212112)(BAAM1122213)(BAAM)(1121224BBAM)(221122115BBAAM)(222122126BBAAM)(121121117BBAAM624511MMMMC2112MMC4321MMC731522MMMMC20

28、22-4-2972算法設(shè)計與分析復雜度分析復雜度分析T(n)=O(nlog7) =O(n2.81) 較大的改進較大的改進22)2/(7) 1 ()(nnnTOnT2022-4-2973算法設(shè)計與分析u傳統(tǒng)方法：O(n3)u分治法: O(n2.81)u更快的方法?Hopcroft和Kerr已經(jīng)證明(1971)，計算2個矩陣的乘積，7次乘法是必要的。因此，要想進一步改進矩陣乘法的時間復雜性，就不能再基于計算22矩陣的7次乘法這樣的方法了?；蛟S應(yīng)當研究或矩陣的更好算法。在Strassen之后又有許多算法改進了矩陣乘法的計算時間復雜性。目前最好的計算時間上界是 O(n2.376)是否能找到O(n2)的

29、算法？目前為止還沒有結(jié)果。2022-4-2974算法設(shè)計與分析凸包問題（相關(guān)定義p84）q什么是凸集合？對于平面的一個點集合（有限或無限），如果以集合中任意兩點p和q為端點的線段都屬于該集合，則稱集合為凸的。q定義： 凸包：一個點集合s的凸包是包含s的最小凸集合。q定理任意包含n2個點（不共線的點）的集合s的凸包是以s中的某些點為頂點的多邊形（如果所有的的店都位于一條直線上，多邊形退化為一條線段，但它的2個端點讓人包含在s中）2022-4-2975算法設(shè)計與分析q假設(shè)點按照x軸排序q找出最左和 最右的極點 (leftmost and rightmost)q遞歸的求凸包的上包:q發(fā)現(xiàn)點 Pmax

30、 是離直線 P1P2直線最遠的點q計算在直線 P1Pmax左側(cè)的上包q計算在直線 PmaxP2左側(cè)的上包q遞歸的計算下包2022-4-2976算法設(shè)計與分析p1p2凸包問題1、最左邊的點p1 1和最右邊的p2 2一定是該集合凸包頂點。2022-4-2977算法設(shè)計與分析p1p2凸包問題2、找到上包的頂點，它是距離直線最遠的點，如果用兩條連接線的話，這個確定了最大的三角形pmaxp1p2。pmax2022-4-2978算法設(shè)計與分析p1p2凸包問題p1max3、找出距離p1pmax左邊最遠的點p3。如此進行下去，直到對應(yīng)的包左邊沒有點p32022-4-2979算法設(shè)計與分析p1p2凸包問題p1m

31、axp2max4、找出PmaxP2左邊最遠的點p4。，按照改方法進行，直到左邊沒有點p42022-4-2980算法設(shè)計與分析p1p2凸包問題p1maxp2max連接所得到的這些點2022-4-2981算法設(shè)計與分析p1p2凸包問題p1maxp2max利用上述求上包的方法求出下包。2022-4-2982算法設(shè)計與分析如何判斷離線段p1p2最遠的點？假設(shè)p3為任意點X1 y1 1X2 y2 1X3 y3 1該行列式的絕對值表示以這3點構(gòu)成的三角形面積，值為正，表示該點位于直線先左側(cè)2022-4-2983算法設(shè)計與分析本章結(jié)束，返回總目錄Chapter 4 減治法Decrease-and-Conqu

32、er2022-4-2985算法設(shè)計與分析減治法q減治法q減治法的類型q減治法與其它方法的區(qū)別返回總目錄2022-4-2986算法設(shè)計與分析減治法q基本思路：q將原問題的實例轉(zhuǎn)化為規(guī)模較小的實例q對規(guī)模較小的實例的求解q將較小的實例的解擴展到原實例q能夠使用自頂向下或者是自底向上q經(jīng)常被稱為歸納法或者是增量法2022-4-2987算法設(shè)計與分析減治法的類型q減去一個常量（一般是）q插入排序 q圖形遍歷算法（深度優(yōu)先查找和廣度優(yōu)先查找）q拓撲排序q減去一個常量因子（一般是一半）q折半查找和二分法q矩陣的冪運算q俄式乘法q減可變規(guī)模q歐幾里得問題q部分選擇2022-4-2988算法設(shè)計與分析減去常量

33、q在這種減治法中，每次減去一個常量因子1。q例如：q插入排序 q圖形遍歷算法（深度優(yōu)先查找和廣度優(yōu)先查找）q拓撲排序2022-4-2989算法設(shè)計與分析插入排序q對數(shù)組A0.n-1，數(shù)組A0.n-2已經(jīng)排好序，然后在數(shù)組中A0.n-2中找一個合適的位置將An-1插入q經(jīng)常使用自底向上（非遞歸）q例如: 對 6, 4, 1, 8, 5進行排序 6 | 4 1 8 5 4 6 | 1 8 5 1 4 6 | 8 5 1 4 6 8 | 5 1 4 5 6 82022-4-2990算法設(shè)計與分析插入排序 2022-4-2991算法設(shè)計與分析插入排序8945689029341745比較45與89的大小

34、2022-4-2992算法設(shè)計與分析插入排序894568902934174545 68 89后移一個位置2022-4-2996算法設(shè)計與分析插入排序8968902934174568比較45與68的大小2022-4-2997算法設(shè)計與分析插入排序8968902934174568將68插入到45后面2022-4-2998算法設(shè)計與分析插入排序89902934174568比較90與前面的數(shù)的大小2022-4-2999算法設(shè)計與分析插入排序89902934174568 89902022-4-29100算法設(shè)計與分析插入排序89902934174568 1 and m if n = 1 n 2n 1 2

35、2022-4-29162算法設(shè)計與分析俄式乘法Compute 20 * 26 n m 20 26 10 52 5 104 104 2 208 + 1 416 416 Note: 把所有n列中包含基數(shù)的m列元素進行相加2022-4-29163算法設(shè)計與分析約瑟夫斯問題q問題的提出2022-4-29164算法設(shè)計與分析減可變因子在這種減治法當中，每次迭代都減小規(guī)模不同的 因子。 例如:q歐幾里得算法q查找問題計算中值和選擇問題2022-4-29165算法設(shè)計與分析歐幾里得求最大公約數(shù)算法歐幾里得算法重復使用公式：gcd(m, n) = gcd(n, m mod n)例如: gcd(80,44) =

36、 gcd(44,36) = gcd(36, 8) = gcd(8,4)余數(shù)為0結(jié)束，取次數(shù)被除數(shù)作為最大公約數(shù)T(n) O(log n)2022-4-29166算法設(shè)計與分析查找問題q在n個數(shù)中查找第k小的元素k = 1 or k = nq中值: k = n/2 例如: 4, 1, 10, 9, 7, 12, 8, 2, 15 中值 = ?q中值是數(shù)理統(tǒng)計中用來求平均值的一個很好的方法q事實上，它比其他類似合并排序的算法要優(yōu)秀很多。2022-4-29167算法設(shè)計與分析a0 a1a2a3aj-1an-1如果有一個數(shù)組an ，現(xiàn)要求出其中第k小元素a0 a1a2a3aian-1A: 以數(shù)組第一個

37、元素為標準，利用快速排序得到此數(shù)值在數(shù)組中的位置是第j個K=j繼續(xù)步驟Aaj-1即為所求求第K小元素2022-4-29168算法設(shè)計與分析411097128215K=9/2=5中值問題2022-4-29169算法設(shè)計與分析411097128215214971281015K=9/2=5中值問題2022-4-29170算法設(shè)計與分析411097128215214971281015S=35,處理列表的右邊部分。K=9/2=5中值問題2022-4-29171算法設(shè)計與分析411097128215214971281015S=35,處理列表的右邊部分。971281015K=9/2=5中值問題2022-4-

38、29172算法設(shè)計與分析411097128215214971281015S=35,處理列表的右邊部分。971281015K=9/2=5879121015中值問題2022-4-29173算法設(shè)計與分析411097128215214971281015S=35,處理列表的左邊部分。中值問題2022-4-29174算法設(shè)計與分析411097128215214971281015S=35,處理列表的左邊部分。8中值問題2022-4-29175算法設(shè)計與分析411097128215214971281015S=35,處理列表的左邊部分。87中值問題2022-4-29176算法設(shè)計與分析411097128215

39、214971281015S=35,處理列表的左邊部分。87中值問題2022-4-29177算法設(shè)計與分析411097128215214971281015S=35,處理列表的左邊部分。8778中值問題2022-4-29178算法設(shè)計與分析411097128215214971281015S=35,處理列表的左邊部分。8778S=5=k,可以停止了。中值問題2022-4-29179算法設(shè)計與分析粘游戲有一堆石子有n粒，兩個人輪流從中拿取1m個石子，最后拿完的為勝者。如果兩個人都使用了正確的方法，誰可能獲勝，第一個人或第二個？ N=0是敗局1=n=m是勝局N=m+1是敗局m+2=n=2m+1是勝局N=

40、2m+2是敗局什么情況下是必勝或者必??？如何選擇策略只要讓對方得到m+1的倍數(shù)就必勝，只需每次拿走n mod m+1即可2022-4-29180算法設(shè)計與分析N=10,m = 4 的粘游戲的圖0512341067892022-4-29181算法設(shè)計與分析q一般粘游戲：有i堆棋子，每堆數(shù)量n1,n2到ni,可以從任意一堆拿走任意個棋子，甚至可以把一堆拿光，最后一個還能走的是贏家？q一個非常妙的解法將每堆棋子數(shù)用2進制數(shù)表示，計算2進制數(shù)位和并忽略進位，如何某人面臨的二進制和 中只有有1存在，就是一個勝局，如果全為0，就是必輸局2022-4-29182算法設(shè)計與分析減治與其它方法的區(qū)別考慮一個冪計

41、算的實例： an q窮舉：an=a*a*aq分治: an=an/2*an/2=q減一: an=an-1*a=q減一個常量因子: a5=a2*a2*a12022-4-29183算法設(shè)計與分析q生成n=4個的格雷碼qP142 2 3,4qP147 32022-4-29184算法設(shè)計與分析本章結(jié)束，返回總目錄變治法Transform-and-Conquer2022-4-29186算法設(shè)計與分析變治法q本章所討論的這組技術(shù)，都是基于變換的思想q變換為同樣問題實例的一個更簡單或者是更方便的實例 (實例化簡)q變換為同樣問題的不同表現(xiàn) (改變表現(xiàn))q變換為另外一個問題的實例，這種問題的算法是已知的 (問題

42、化簡)2022-4-29187算法設(shè)計與分析變治法實例q實例化簡q改變表現(xiàn)q問題化簡返回總目錄2022-4-29188算法設(shè)計與分析實例化簡 預排序q將實例變換為同樣問題實例的一個更簡單或者是更方便的實例q預排序q如果列表有序，許多涉及到列表的問題就更加容易求解q查找問題q計算中值 (選擇問題)q檢查元素的唯一性 (元素唯一性)q其它：q拓撲排序解決了許多關(guān)于無環(huán)有向圖的問題。q預排序用于解決幾何問題.2022-4-29189算法設(shè)計與分析排序能夠有多快 ?q依賴于所選用的排序算法的效率。q理論：沒有一種基于比較的普通排序算法，在最壞的情況下效率能夠超過log2 n! n log2 n q注意

43、: nlog2 n次比較也可以對含有n個元素的數(shù)組進行排序（合并排序）2022-4-29190算法設(shè)計與分析基于預排序的查找q問題: 在數(shù)組 A0.n-1中查找給定的K值 q基于預排序的算法:q第一步： 對數(shù)組進行排序q第二步： 應(yīng)用折半查找 q時間效率: (nlog n) + O(log n) = (nlog n) q為 什 么 我 們 要 對 字 典 、 電 話 簿 等 東 西 排 序 ?2022-4-29191算法設(shè)計與分析檢查數(shù)組元素的唯一性q基于預排序的算法q第一步: 對數(shù)組進行排序 (例如：歸并排序)q第二步: 檢查元素之間的連續(xù)性q時間效率: (nlogn) + O(n) = (

44、nlogn)q蠻力法q比較數(shù)組中所有的元素q時間效率: O(n2) q另外一種算法? q哈希2022-4-29192算法設(shè)計與分析改變表現(xiàn)高斯消去法q思路: 把n個線性方程構(gòu)成的n元聯(lián)立方程組變換為一個等價的方程組q變形:把n個線性方程構(gòu)成的n元聯(lián)立方程組變換為一個上三角系數(shù)矩陣q從最后一個方程，可以立即求出最后一個方程的的解，然后代入倒數(shù)第二個，就可以求出倒數(shù)第二個方程的解，依次類推，從而求出第一個方程的解 a11x1 + a12x2 + + a1nxn = b1 a1,1x1+ a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 a22x2

45、+ + a2nxn = b2 an1x1 + an2x2 + + annxn = bn annxn = bn 2022-4-29193算法設(shè)計與分析高斯消去法經(jīng)過一系列的初等變換可以從一個具有任意系數(shù)矩陣的方程組推導出一個具有上三角系數(shù)矩陣的等價方程組（不改變系數(shù)矩陣的答案): forfor i 1 to n-1 dodo 交換方程組中兩個方程的位置。 把一個方程替換為它的非零倍。 把一個方程替換為他和另一個方程倍數(shù)之間的和或差2022-4-29194算法設(shè)計與分析高斯消去法S o l v e 2 x1 - 4 x2 + x3 = 6 3x1 - x2 + x3 = 11 x1 + x2 -

46、x3 = -3 高斯消去法 2 -4 1 6 2 -4 1 6 3 -1 1 11 row2 (3/2)*row1 0 5 -1/2 2 1 1 -1 -3 row3 (1/2)*row1 0 3 -3/2 -6 row3(3/5)*row2 2 -4 1 6 0 5 -1/2 2 0 0 -6/5 -36/5 回代 x3 = (-36/5) / (-6/5) = 6 x2 = (2+(1/2)*6) / 5 = 1 x1 = (6 6 + 4*1)/2 = 22022-4-29195算法設(shè)計與分析高斯消去法的偽代碼和時間效率第一步: 上三角矩陣的簡化for i 1 to n-1 do for

47、 j i+1 to n do for k i to n+1 do Aj, k Aj, k - Ai, k * Aj, i / Ai, i /improve!第二步: 回代for j n downto 1 do t 0 for k j +1 to n do t t + Aj, k * xk xj (Aj, n+1 - t) / Aj, j 效率: (n3) + (n2) = (n3)2022-4-29196算法設(shè)計與分析查找問題q問題: 給定一組數(shù)據(jù)S，和一個元素K，如果S中包含K，則要找到K在S中的位置，在查找的過程中要考慮以下問題：q文件大小 (i內(nèi)部文件 vs. 外部文件)q動態(tài)數(shù)據(jù) (靜

48、態(tài) vs. 動態(tài))q字典操作 (動態(tài)數(shù)據(jù)):q查找q插入q刪除2022-4-29197算法設(shè)計與分析查找算法分類q列表查詢q順序查找q折半查找q插值查找q查找樹 q二分查找樹q平衡查找樹: AVL trees, red-black treesq多路查找樹: 2-3 trees, 2-3-4 trees, B treesq哈希q開散列 (分離鏈)q閉散列 (開式尋址)2022-4-29198算法設(shè)計與分析二叉查找樹KK2022-4-29199算法設(shè)計與分析 q二叉平衡s樹（平衡查找樹）每棵樹的平衡因子定義為該節(jié)點的左子樹和右子樹的高度差，這個平衡因子只能為0，1或-1。（空樹的高度定義為-1）2

49、022-4-29200算法設(shè)計與分析平衡查找樹 （AVL）在最壞情況下，平衡查找樹的效率是線性的。從而退化到了嚴重不平衡的情。下面是兩套解決方案:q 把一棵不平衡的二叉樹轉(zhuǎn)換為一棵平衡的二叉樹q AVL treesq red-black treesq 允許一棵查找樹的單個節(jié)點不止包含一個元素q 2-3 treesq 2-3-4 treesq B-trees2022-4-29201算法設(shè)計與分析平衡樹（AVL樹） 一棵 AVL tree 是一棵二叉查找樹，其中每個結(jié)點的平衡因子定義為該節(jié)點左子樹和右子樹的高度差，這個平衡因子要么為0，要么為+1.要么為-1（一棵空樹的高度定義為-1）520124

50、72(a)10181010-100520472(b)10280010-102022-4-29202算法設(shè)計與分析.非平衡二叉樹的平衡處理可以對非平衡二叉樹進行平衡處理，使其變成一棵平衡二叉樹。下面將分四種情況討論平衡處理。2022-4-29203算法設(shè)計與分析（1）LL型型 的處理的處理(左左型左左型)如圖所示，在C的左孩子B上扦入一個左孩子結(jié)點A，成為不平衡的二叉樹序樹。這時的平衡處理為：將C順時針旋轉(zhuǎn)，成為B的右子樹，待扦入結(jié)點A作為B的左子樹。 平衡外理 1 A B C 0 2 C B A 0 0 0 LL 型平衡外理 2022-4-29204算法設(shè)計與分析2）LR型的處理型的處理(左右

51、型左右型)如圖所示，在C的左孩子A上扦入一個右孩子B，使的C的平衡因子由1變成了2，成為不平衡的二叉排序樹。這是的平衡處理為：將B變到A與C 之間，使之成為LL型，然后按第(1)種情形LL型處理。 0 -1 C A B 2 0 1 C A B 2 B 0 0 C A 0 平衡處理 旋轉(zhuǎn) LR 型平衡處理 2022-4-29205算法設(shè)計與分析ABCEFDABCEFDABCEFD以左子樹的右子樹根節(jié)點E為中心，逆時鐘旋轉(zhuǎn)成ll型仍然以E為中心，順時鐘旋轉(zhuǎn)LR型的普通形狀的轉(zhuǎn)化GGG2022-4-29206算法設(shè)計與分析3）RR型的處理型的處理(右右型右右型)如圖所示，在A的右孩子B上扦入一個右孩

52、子C，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹。這時的平衡處理為：將A逆時針旋轉(zhuǎn)，成為B的左子樹，而原來B的左子樹則變成A的右子樹，待扦入結(jié)點C成為B的右子樹。 平衡處理 -1 C B A 0 -2 C B A 0 0 0 RR型平衡處理 2022-4-29207算法設(shè)計與分析4）RL型的處理型的處理(右左型右左型)如 圖所示，在A的右孩子C上扦入一個左孩子B，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹。這時的平衡處理為：將B變到A與C之間，使之成為RR型，然后按第(3) 種情形RR型處理。 平衡處理 C B A 0 0 0 RL 型平衡處理 -1 -2 C B A B

53、0 1 -2 A 旋轉(zhuǎn) C 2022-4-29208算法設(shè)計與分析以右子樹的左子樹根節(jié)點D為中心，順時鐘旋轉(zhuǎn)成RR型仍然以D為中心，逆順時鐘旋轉(zhuǎn)RL型的普通形狀的轉(zhuǎn)化ABCDEFABCDEFABCEDFGGG2022-4-29209算法設(shè)計與分析例，給定一個關(guān)鍵字序列4,5,7,2 ,1,3,6，試生成一棵平衡二叉樹。分析：平衡二叉樹實際上也是一棵二叉排序樹，故可以按建立二叉排序樹的思想建立，在建立的過程中，若遇到不平衡，則進行相應(yīng)平衡處理，最后就可以建成一棵平衡二叉樹。具體生成過程見圖。 (a) 插入插入 4 (b) 插入插入 5 (c) 插入插入 7 RR 型型 4 0 4 5 0 -1

54、7 4 5 -2 -1 0 0 0 4 5 7 0 2022-4-29210算法設(shè)計與分析 LL 型型 (d)插入插入 2 (e)插入插入 1 4 2 5 7 1 0 0 0 0 0 4 2 5 7 1 0 0 1 2 2 4 2 5 7 0 0 1 1 -1 5 2 1 4 3 7 2 0 1 0 0 5 2 1 4 3 7 -1 0 0 0 0 0 LR 型型 (f)插入插入 3 2022-4-29211算法設(shè)計與分析 5 2 1 4 3 7 -2 -1 0 1 0 0 6 0 RL 型 0 6 2 1 4 3 7 0 0 0 0 0 5 0 (g) 插入 6 平衡二叉樹的生成過程 202

55、2-4-29212算法設(shè)計與分析qh 1.4404 log2 (n + 2) - 1.3277 平均高度: 1.01 log2n + 0.1 n比較大的情況q查詢和插入的效率是 O(log n)q刪除更加復雜，但是效率仍然 O(log n)q缺點: q頻繁的旋轉(zhuǎn)q復雜性q簡單的思想: 紅黑樹 (子樹的高度相差兩倍) 平衡樹（AVL樹）2022-4-29213算法設(shè)計與分析多路查找樹定義：多路查找樹是一種允許在同一個節(jié)點上有多個鍵的樹. k1 k2 kn-1 k1k1, k2 ) kn-12022-4-29214算法設(shè)計與分析2-3 Tree 定義 2-3 tree 是一個具有以下特征的查找樹：

56、q 有兩個或三個節(jié)點q 高度平衡 (所有的葉子都在同一層)構(gòu)造一棵2-3樹是將鍵成功的插入到樹中, 總是把新鍵插到一個葉子里. 如果葉子是3個節(jié)點,就把葉子分裂成兩個節(jié)點，中間的鍵提升到原來葉子的父母中去。KK , K12(K , K )122-node3-node K K122022-4-29215算法設(shè)計與分析95, 95, 8, 98952-3 Tree利用9，5，8 ，2，3，4，7建立一棵2-3樹2022-4-29216算法設(shè)計與分析95, 95, 8, 98952, 3, 589已達到三個節(jié)點中間鍵3提升為根節(jié)點2-3 Tree利用9，5，8 ，2，3，4，7建立一棵2-3樹202

57、2-4-29217算法設(shè)計與分析95, 95, 8, 98952，589已達到三個節(jié)點中間鍵3提升為根節(jié)點2-3 Tree利用9，5，8 ，2，3，4，7建立一棵2-3樹2022-4-29218算法設(shè)計與分析95, 95, 8, 98952, 3, 5893, 89252-3 Tree利用9，5，8 ，2，3，4，7建立一棵2-3樹 2022-4-29219算法設(shè)計與分析3, 8924, 52-3 Tree 利用9，5，8 ，2，3，4，7建立一棵2-3樹2022-4-29220算法設(shè)計與分析3, 8924, 53, 84, 5, 729已達到三個節(jié)點中間鍵5提升為根節(jié)點2-3 Tree 利用

58、9，5，8 ，2，3，4，7建立一棵2-3樹2022-4-29221算法設(shè)計與分析3, 8924, 53, 84, 5, 7293, 5, 82479已達到三個節(jié)點中間鍵5提升為根節(jié)點2-3 Tree 利用9，5，8 ，2，3，4，7建立一棵2-3樹2022-4-29222算法設(shè)計與分析3, 8924, 53, 84, 5, 7293, 5, 8247953428972-3 Tree 利用9，5，8 ，2，3，4，7建立一棵2-3樹2022-4-29223算法設(shè)計與分析qlog3 (n + 1) - 1 h log2 (n + 1) - 1q查找，插入和刪除 ：(log n)q2-3 tree

59、的思想概括說來就是允許一個節(jié)點上可以同時包含多個鍵。 q2-3-4 trees qB-trees2-3 Tree 2022-4-29224算法設(shè)計與分析堆和堆排序q堆可以定義為一棵二叉樹，樹的節(jié)點中包含鍵（每個節(jié)點一個鍵），并且滿足下面兩個條件:q這棵二叉樹是基本完備的, 意味著,樹的每一層都是滿的，除了最后一層的最后一個元素有可能空缺。q每個結(jié)點的鍵都要大于或等于它子女的鍵，即父母優(yōu)勢2022-4-29225算法設(shè)計與分析堆的定義Note: Note: 在堆中，鍵值是從上到下排序的在堆中，鍵值是從上到下排序的 ( (從根到葉子的路從根到葉子的路徑徑 ) )。而且鍵值之間不存在從左到右的次序。

60、而且鍵值之間不存在從左到右的次序105427110527110562712022-4-29226算法設(shè)計與分析堆的一些重要屬性q只存在一棵n個節(jié)點的完全二叉樹。它的高度為等于 log2 nq堆的根總包含了堆的最大元素q堆 的 一 個 節(jié) 點 以 及 該 結(jié) 點 的 子 孫 也 是 一 個 堆q可以用數(shù)組來實現(xiàn)一個堆2022-4-29227算法設(shè)計與分析堆的概念q可以用數(shù)組來按照從上到下，從左到右的方式記錄堆中的元素 (為了方便起見，將數(shù)組1到n的位置上存放堆元素)。Example:q節(jié)點j的左孩子位于 2jq節(jié)點j的右孩子位于 2j+1q父母節(jié)點j位于 j/2 q父母節(jié)點的鍵位于數(shù)組的前n/2