算法設(shè)計(jì)01第一講

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

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

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

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

5、hniques and Analysis線性搜索 主要思想 掃描數(shù)組A，依次將每個(gè)元素和x進(jìn)行比較. 如何經(jīng)過j次比較，1j n，找到x, x=Aj，則返回下標(biāo) j否則返回下標(biāo)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的后面 我們進(jìn)一步在子集Amid+1high中搜索x Algorithms Design Techniques and AnalysisAlgorithm 1.2 BINARYSEARCHInput: 數(shù)組A 1n包含n個(gè)非遞減次序的元，查找元素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 例子我們?cè)谙旅鏀?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í)候達(dá)到最大的比較次數(shù)呢？Proof :p5在while循環(huán)的第j次循環(huán)時(shí)，剩余元素的數(shù)目是n/2j-1。循環(huán)最大次數(shù)是滿足條件n/2j-1=1時(shí)的j值，因此, 1 n/2j-1 2 j= logn+

9、1Algorithms Design Techniques and Analysis1.5 選擇排序 基本思想:設(shè) A1.n為包含n個(gè)元素的數(shù)組首先,我們找到數(shù)組中的最小元素,將它存在A1. 接著,我們從剩下的n-1個(gè)元素中找到最小的元素,將它存在 A2.重復(fù)以上過程,知道整個(gè)數(shù)組中第二大的元素存在An-1,則算法停止.Algorithms Design Techniques and AnalysisAlgorithm 1.4 SELECTIONSORTInput: 包含n個(gè)元素的數(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個(gè)最小元素 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 合并兩個(gè)有序的數(shù)組 問題描敘 假設(shè)我們有一個(gè)數(shù)組 A1m 和三個(gè)下標(biāo)p, q 和 r, 其中 1pqrm. 該數(shù)組的兩個(gè)子部分Apq 和 Aq+1r 都是非遞減排序. 我們需要重新調(diào)整A中的元素,使得Apr 中的元素非遞減排序.Algorithms Design Techniques and Analysis 例子合并兩個(gè)子數(shù)組 2, 3, 66 and 7, 11, 13, 45, 57.2366711134557stk2371113455766end!Alg

12、orithms Design Techniques and Analysis Algorithm 1.3 MERGEInput:數(shù)組 A1m 和三個(gè)下標(biāo)p, q 和 r, 其中 1pqrm. 該數(shù)組的兩個(gè)子部分Apq 和 Aq+1r 都是非遞減排序Output: Apr 中的元素非遞減排序. ment: B pr 是一個(gè)輔助數(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 :對(duì)于合并長(zhǎng)度為n1 和 n2 的兩個(gè)數(shù)組(n1n2,n=n1+n2),merge算法的元素比較次數(shù)介于n1 和 n-1之間. 特別的是,如果兩個(gè)數(shù)組的大小為n/2, 元素比較次數(shù)介于 n/2 和 n-1之間. Observation 1.2:元素賦值次數(shù)為 2n.Algorithms Design Techniques and Ana

14、lysis1.7 從底向上合并排序 基本思想直接在數(shù)組上進(jìn)行操作, 利用兩個(gè)有序數(shù)組合并的算法初始化變量, s=1, 每一次循環(huán)s=2*s i+1, i + s 和 i+t 定義兩個(gè)需要合并的子序列的邊界. Algorithms Design Techniques and AnalysisAlgorithm 1.6 BOTTOMUPSORTInput: 包含n個(gè)元素的數(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符號(hào)定義1.2：把函數(shù)f(n)包含在O(g(n)，記作f(n)O(g(n)。它成立的條件是：對(duì)于所有足夠大的n，f(n)的上界由g(n)的常數(shù)倍所確定即，存在常數(shù)c0和一個(gè)自然數(shù)n0，使得 nn0, f(n) c g(n).例：證明100n+5 O(n2)100n+5 100n+n(當(dāng)n 5)=101n 101n2 取c=101，n0=5100n+5 100n+5n(當(dāng)n 1)=105n 105n2 取c=105，n0=1符號(hào)定義1.2：把函數(shù)f(n)包含在(g(n)，記作

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

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

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

19、echniques and Analysis1.11 怎么估算算法的運(yùn)行時(shí)間計(jì)算迭代的次數(shù).計(jì)算基本操作的頻度.使用遞推關(guān)系A(chǔ)lgorithms Design Techniques and Analysis1.11.1 計(jì)算迭代的次數(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包含兩個(gè)嵌套循環(huán)和一個(gè)變量count,這個(gè)變量用來對(duì)算法執(zhí)行的迭代次數(shù)計(jì)數(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計(jì)算基本運(yùn)算的頻度Definition 1.6:如果算法中的一個(gè)元運(yùn)算具有最高頻率, 所以其他元運(yùn)算頻率均在他的頻率的常數(shù)倍內(nèi),則在這個(gè)元運(yùn)算稱為基本運(yùn)算Example: MERGE算法

21、中的元素賦值是基本運(yùn)算.注意元素比較一般意義下不是基本運(yùn)算, 極端情況下可能只有一次1.11.3 使用遞推關(guān)系 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