1、2020/7/15,0,陳衛(wèi)東 華南師范大學(xué)計(jì)算機(jī)科學(xué)系,Algorithms :Design Techniques and Analysis 算法設(shè)計(jì)技巧與分析,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,遞歸算法的基本模式（求解問(wèn)題） 遞歸算法的 優(yōu)點(diǎn) 例1 選擇排序 例2 直接

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

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

4、,問(wèn)題： 要求對(duì) n個(gè)數(shù)的序列L=a1, a2 , , an進(jìn)行排序，其中每個(gè)數(shù)恰好由k位數(shù)字組成，每位數(shù)字均取自0,1,9。 算法思想：對(duì)于k使用歸納法。 例子 Algorithm 5.3 RADIXSORT 算法的時(shí)空復(fù)雜性分析 時(shí)間復(fù)雜度： (kn) 空間復(fù)雜度： (n),2020/7/15,9,Integer Exponentiation(求整數(shù)次冪),問(wèn)題： 求實(shí)數(shù)x的n次冪，即xn ，其中n為一個(gè)非負(fù)整數(shù)。 算法思想 計(jì)算xn 計(jì)算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 算法的時(shí)空復(fù)雜度： (log n),2020/7/15,10,Evaluating Polynomials(多項(xiàng)式求值),問(wèn)題： 求下列實(shí)系數(shù)多項(xiàng)式的值： Pn(x)=anxn+ an-1xn-1 + + a1x + a0 算法思想（Horners rule） Pn(x)= xPn-1(x) + a0 Algorithm 5.6 HORNER 算法的時(shí)空復(fù)雜性分析 時(shí)間復(fù)雜度： (n),2020/7/15,11,Generating Permutations(生成排列),問(wèn)題： 要求產(chǎn)生1,2,n的所有排列。 算法1 算法思想 12,3,n的排列， 21,3,n的排列，

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

7、(n2) 算法2：排序法 時(shí)間復(fù)雜度: (n log n) 算法3：找中元素法（finding the median） 時(shí)間復(fù)雜度: (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