算法分析與設計5

1、2020/7/15,0,陳衛(wèi)東 華南師范大學計算機科學系,Algorithms :Design Techniques and Analysis 算法設計技巧與分析,2020/7/15,1,Chapter 5 Induction,Introduction Radix Sort Integer Exponentiation Evaluating Polynomials Generating Permutations Finding the Majority Element,2020/7/15,2,Introduction,遞歸算法的基本模式（求解問題） 遞歸算法的 優(yōu)點 例1 選擇排序 例2 直接

2、插入排序,2020/7/15,3,遞歸算法的基本模式（求解問題）,1. n=1, f(1) (直接求解)； 2. 若f(k)（kn）可求，則 利用f(1)、f(n-1)得f(n)。 注：一般來說，求f(k)（kn）比求f(n)容易。若有辦法由f(1)、f(n-1)得到f(n)即可。 歸納原理,2020/7/15,4,遞歸算法的基本模式（求解問題）,遞歸算法的框架： f(n) n=1, f(1) (直接求解)； n1, 利用f(1)、f(n-1)求得f(n)； 注：關鍵步驟是由f(1)、f(n-1)得到f(n)。 其正確性可使用歸納法來證明。,2020/7/15,5,遞歸算法的特點,遞歸算法的優(yōu)

3、點： 1. 讀寫簡明； 2. 算法的正確性易于用數(shù)學歸納法來證； 3. 算法的復雜性往往可利用遞歸關系來分析 缺點： 1. 算法的執(zhí)行流程不易理解； 2. 遞歸調用往往需要額外的時空開銷,2020/7/15,6,例1 選擇排序,算法的基本框架： Ain排序 若ni, 將Ain中最小元素找出，并換至Ai處； Ai+1n排序; 算法遞歸調用圖 算法的時空復雜性分析,2020/7/15,7,例2 直接插入排序,算法的基本框架： A1i排序 若i1, A1i-1排序; 將Ai插入到A1i-1中的適當位置處； 算法遞歸調用圖 算法的時空復雜性分析,2020/7/15,8,Radix Sort（基數(shù)排序）

4、,問題： 要求對 n個數(shù)的序列L=a1, a2 , , an進行排序，其中每個數(shù)恰好由k位數(shù)字組成，每位數(shù)字均取自0,1,9。 算法思想：對于k使用歸納法。 例子 Algorithm 5.3 RADIXSORT 算法的時空復雜性分析 時間復雜度： (kn) 空間復雜度： (n),2020/7/15,9,Integer Exponentiation(求整數(shù)次冪),問題： 求實數(shù)x的n次冪，即xn ，其中n為一個非負整數(shù)。 算法思想 計算xn 計算xm ； / m=n/2 若n是偶數(shù)，則xn =(xm)2, 若n是奇數(shù)，則xn =x(xm)2 Algorithm 5.4 EXPREC Algori

5、thm 5.5 EXP 算法的時空復雜度： (log n),2020/7/15,10,Evaluating Polynomials(多項式求值),問題： 求下列實系數(shù)多項式的值： Pn(x)=anxn+ an-1xn-1 + + a1x + a0 算法思想（Horners rule） Pn(x)= xPn-1(x) + a0 Algorithm 5.6 HORNER 算法的時空復雜性分析 時間復雜度： (n),2020/7/15,11,Generating Permutations(生成排列),問題： 要求產(chǎn)生1,2,n的所有排列。 算法1 算法思想 12,3,n的排列， 21,3,n的排列，

6、 n1,2,n-1的排列。 Algorithm 5.7 PERMUTATIONS1 算法時間復雜度: (nn!),2020/7/15,12,Generating Permutations(生成排列),算法2 算法思想 n n ， n。 Algorithm 5.8 PERMUTATIONS2 算法時間復雜度: (nn!),2020/7/15,13,Finding the Majority Element(找主元素),問題 序列A1.n中是存在主元素？若有請找出來。 注：A中主元素是指在A中出現(xiàn)次數(shù)多于n/2次的元素。 算法1：窮舉法（the brute-force method） 時間復雜度:

7、(n2) 算法2：排序法 時間復雜度: (n log n) 算法3：找中元素法（finding the median） 時間復雜度: (n),2020/7/15,14,Finding the Majority Element(找主元素),算法4： 算法思想 Observation 5.1 If two different elements in the original sequence are removed, then the majority in the original sequence remains the majority in the new sequence. Algorithm