算法設計01第一講

1、Algorithms Design Techniques and Analysis 算法設計技巧與分析Algorithms Design Techniques and Analysis教學目的、內容和形式目的:掌握算法的特性；掌握分析算法的基本方法；通過學習常用的精巧算法,掌握設計算法的基本方法.教材算法設計技巧與分析，M.H.Alsuwaiyel, 電子工業(yè)出版社.參考書: 算法設計與分析, 王曉東編著, 2003, 清華大學出版社.計算機算法基礎，余詳宣等編著，2003年，華中科技大學出版社學習形式:自學、講授相結合.Algorithms Design Techniques and Ana

2、lysis本書主要內容Part 1 算法的基本概念算法分析概念數(shù)學基礎數(shù)據結構堆與不相交集Part 2 基于遞歸的技術歸納分治動態(tài)規(guī)劃Part 3 最先割技術 . 貪心算法Part 4 問題復雜性 NP完全問題Part 5 克服困難性 回溯法Algorithms Design Techniques and Analysis第一章算法分析的基本概念Algorithms Design Techniques and Analysis本章的主要內容引言搜索問題二分搜索排序問題合并兩個兩個有序表選擇排序從底向上合并排序算法分析概念時間復雜度, 空間復雜度最優(yōu)算法如何估算算法的運行時間最壞和平均情況分析A

3、lgorithms Design Techniques and Analysis 什么是算法? 算法是定義好的能夠完成一定任務的有限指令集合，通常它由一個初始化狀態(tài)，終止于一個對應的可識別的結束狀態(tài)。算法通常由計算機程序來實現(xiàn)，算法設計的錯誤可能導致程序運行時的失敗。QAAlgorithms Design Techniques and Analysis算法的5個特征有效性算法必須在有限的時間能夠完成，甚至用紙和筆完成確定性算法的每一步能夠清楚的定義.有限性算法能夠在有限的步驟完成Input 算法有0個或者多個輸入5.Output 算法有一個或者多個輸出滿足有效性，確定性，輸入，輸出特征的程序是

4、一個過程而不是算法,舉例：操作系統(tǒng)是過程而不是算法Algorithms Design Techniques and Analysis算法的比較對于同一個問題，可能存在多個算法。那么那個算法好一點呢？解決問題所需要的時間和空間其它一些所需要的資源，例如通訊開銷，處理器的數(shù)目，等等QAlgorithms Design Techniques and Analysis1.3 二分搜索搜索問題描述設A1.n 為一個包含n個元素的數(shù)組. 考慮這樣的問題：判斷給定元素X是否在A中。結果就是找到這個元素的下標j, 1j n，使得x=A j ；如果不存在這個元素,j=0Algorithms Design Tec

5、hniques and Analysis線性搜索 主要思想 掃描數(shù)組A，依次將每個元素和x進行比較. 如何經過j次比較，1j n，找到x, x=Aj，則返回下標 j否則返回下標0，表示搜索失敗了Algorithms Design Techniques and AnalysisAlgorithm 1.1 LINEARSEARCHInput: An array A 1n of n elements and an element x. Output: j if x = A j, 1 j n, and 0 otherwise. 1. j 1 2.while (j A mid. 如何在數(shù)組A中, 那么X

6、在A mid的后面 我們進一步在子集Amid+1high中搜索x Algorithms Design Techniques and AnalysisAlgorithm 1.2 BINARYSEARCHInput: 數(shù)組A 1n包含n個非遞減次序的元，查找元素x. Output: j if x = A j, 1 j n, and 0 otherwise. 1.low1; high n; j 0 2.while (low high) and (j = 0) 3. mid low+high/2 4. if x = A mid then j mid 5. else if x A mid then hi

7、gh mid 1 6. else low mid + 1 7. end while 8.return jAlgorithms Design Techniques and Analysis 例子我們在下面數(shù)組中搜索 x=22 A1.14 = 1,4,5,7,8,9,10,12,15,22,23,27,32,35.12345678910111213141457891012152223273235lowhighmid1147814118109101010success!Algorithms Design Techniques and Analysis例子在下面數(shù)組中搜索 x=21 A1.14 =1,

8、4,5,7,8,9,10,12,15,22,23,27,32,35.12345678910111213141457891012152223273235lowhighmid1147814118109101010109failure!Algorithms Design Techniques and Analysis二分搜索算法分析 定理: 規(guī)模為n的二分搜索算法中元素比較次數(shù)最多 logn+1. 什么時候達到最大的比較次數(shù)呢？Proof :p5在while循環(huán)的第j次循環(huán)時，剩余元素的數(shù)目是n/2j-1。循環(huán)最大次數(shù)是滿足條件n/2j-1=1時的j值，因此, 1 n/2j-1 2 j= logn+

9、1Algorithms Design Techniques and Analysis1.5 選擇排序 基本思想:設 A1.n為包含n個元素的數(shù)組首先,我們找到數(shù)組中的最小元素,將它存在A1. 接著,我們從剩下的n-1個元素中找到最小的元素,將它存在 A2.重復以上過程,知道整個數(shù)組中第二大的元素存在An-1,則算法停止.Algorithms Design Techniques and AnalysisAlgorithm 1.4 SELECTIONSORTInput: 包含n個元素的數(shù)組 A 1.n .Output: A 1.n 中的元素非遞減排列 1. for i1 to n-1 2. k i

10、 3. for ji+1 to n 找到第 it個最小元素 4. if A j0) and (Ajx) 5. Aj+1Aj 6. jj-1 7. end while 8. Aj+1=x 9.end forAlgorithms Design Techniques and Analysis An exampleA1.11 = 6,10,9,5,3,11,4,8,1,2,76109531148127ix=10j99Algorithms Design Techniques and Analysis算法分析 Observation 1.4: 插入排序的元素比較次數(shù)介于n-1 和 n(n-1)/2 之間.

11、 元素賦值次數(shù)等于元素比較次數(shù)加上 n-1.Algorithms Design Techniques and Analysis1.4 合并兩個有序的數(shù)組 問題描敘 假設我們有一個數(shù)組 A1m 和三個下標p, q 和 r, 其中 1pqrm. 該數(shù)組的兩個子部分Apq 和 Aq+1r 都是非遞減排序. 我們需要重新調整A中的元素,使得Apr 中的元素非遞減排序.Algorithms Design Techniques and Analysis 例子合并兩個子數(shù)組 2, 3, 66 and 7, 11, 13, 45, 57.2366711134557stk2371113455766end!Alg

12、orithms Design Techniques and Analysis Algorithm 1.3 MERGEInput:數(shù)組 A1m 和三個下標p, q 和 r, 其中 1pqrm. 該數(shù)組的兩個子部分Apq 和 Aq+1r 都是非遞減排序Output: Apr 中的元素非遞減排序. ment: B pr 是一個輔助數(shù)組 2.sp; t q + 1; k p 3.while s q and t r 4. if A s A t then 5. B k A s; ss+1 6. else B k A t; tt+1 7. end if 8. kk+1 9. end while 10. if

13、 s = q + 1 then B kr A tr 11.else B kr A sq 12. end if 13. A pr B pr Algorithms Design Techniques and Analysis算法分析 Observation 1.1 :對于合并長度為n1 和 n2 的兩個數(shù)組(n1n2,n=n1+n2),merge算法的元素比較次數(shù)介于n1 和 n-1之間. 特別的是,如果兩個數(shù)組的大小為n/2, 元素比較次數(shù)介于 n/2 和 n-1之間. Observation 1.2:元素賦值次數(shù)為 2n.Algorithms Design Techniques and Ana

14、lysis1.7 從底向上合并排序 基本思想直接在數(shù)組上進行操作, 利用兩個有序數(shù)組合并的算法初始化變量, s=1, 每一次循環(huán)s=2*s i+1, i + s 和 i+t 定義兩個需要合并的子序列的邊界. Algorithms Design Techniques and AnalysisAlgorithm 1.6 BOTTOMUPSORTInput: 包含n個元素的數(shù)組 A 1.n Output: A 1.n 按照非遞減排序. 1. t1 2.while tn 3. s t; t2s; i0 4. while i + t n 5. MERGE(A, i+1, i + s, i+t) 6. i

15、i+t 7. end while 8. if i + s 0的情況下都包含在(n2)中n2+sina，n2+logn ?O符號定義1.2：把函數(shù)f(n)包含在O(g(n)，記作f(n)O(g(n)。它成立的條件是：對于所有足夠大的n，f(n)的上界由g(n)的常數(shù)倍所確定即，存在常數(shù)c0和一個自然數(shù)n0，使得 nn0, f(n) c g(n).例：證明100n+5 O(n2)100n+5 100n+n(當n 5)=101n 101n2 取c=101，n0=5100n+5 100n+5n(當n 1)=105n 105n2 取c=105，n0=1符號定義1.2：把函數(shù)f(n)包含在(g(n)，記作

16、f(n) (g(n)。它成立的條件是：對于所有足夠大的n，f(n)的下界由g(n)的常數(shù)倍所確定即，存在常數(shù)c0和一個自然數(shù)n0，使得 nn0, f(n) c g(n).例：證明n3 (n2) 當n 0時，n3 n2 取c=1，n0=1符號定義1. 3：把函數(shù)f(n)包含在(g(n)，記作f(n) (g(n)。它成立的條件是：對于所有足夠大的n，f(n)的下界，上界由g(n)的常數(shù)倍所確定即，存在常數(shù)c0和一個自然數(shù)n0，使得 nn0, c1g(n) f(n) c2g(n).例：證明n(n-1)/2 (n2)當n 0時，n(n-1)/2=n2/2-n/2 n2/2 證明上界n(n-1)/2=n

17、2/2-n/2 n2/2-n2/2(當n 2)=n2/4 下界 取c2 =1/2，c1=1/4及n0=2利用極限比較增長率比較兩個特定函數(shù)的增長率情況意味著t(n) O(g(n)情況意味著t(n) (g(n)情況意味著t(n) (g(n)利用基于極限的方法比基于定義的方法更方便洛必達法則史特林公式利用極限比較增長率例：比較log2n和 的增長次數(shù)例：比較n!和2n的增長率Algorithms Design Techniques and Analysis1.9 空間復雜度為了求解問題的實例而執(zhí)行的計算步驟所需要的內存空間,它不包括分配用來存儲輸入的空間.換句話說,就是算法需要的工作空間不包括輸入

18、大小的原因是為了區(qū)分那些在整個計算過程中占用了少于線形空間的算法.Algorithms Design Techniques and Analysis例子在線性搜索算法中,只需要一個內存單元用來存儲搜索結果.我們可以說需要的空間為(1). 二分搜索,選擇排序和插入排序的情況一樣.更多的例子 (see P20)Algorithms Design Techniques and Analysis1.10 最優(yōu)算法定義:一般說來,如果我們能夠這個證明解決問題的時間復雜度為(f(n),那么一個時間復雜度為O(f(n)的算法稱為一個最優(yōu)算法(這個定義沒有考慮空間復雜度)Algorithms Design T

19、echniques and Analysis1.11 怎么估算算法的運行時間計算迭代的次數(shù).計算基本操作的頻度.使用遞推關系Algorithms Design Techniques and Analysis1.11.1 計算迭代的次數(shù)例子:Input:n=2k, for some positive integer k.Output: count=number of times Step 4 is executed.1.count02. while n13.for j1 to n4. countcount+15.end for6.nn/27. end while8. return count A

20、lgorithms Design Techniques and Analysis 分析COUNT1包含兩個嵌套循環(huán)和一個變量count,這個變量用來對算法執(zhí)行的迭代次數(shù)計數(shù), 這里 n=2k, 其中 k為正整數(shù).while循環(huán)執(zhí)行 k+1次,這里 k=logn. For循環(huán)執(zhí)行n次,之后是 n/2, n/4,.,1. Algorithms Design Techniques and Analysis1.11.2計算基本運算的頻度Definition 1.6:如果算法中的一個元運算具有最高頻率, 所以其他元運算頻率均在他的頻率的常數(shù)倍內,則在這個元運算稱為基本運算Example: MERGE算法

21、中的元素賦值是基本運算.注意元素比較一般意義下不是基本運算, 極端情況下可能只有一次1.11.3 使用遞推關系 Input: An array A1.n of n elements sorted in nondecreasing order and an element x. Output: j if x=Aj, 1j n, and 0 otherwise. 1. binarysearch(1,n)Procedure binarysearch(low,high) 1. if lowhigh then return 0 2. else 3. mid (low+high)/2 4. if x=Amid then retur