離散數(shù)學(xué)算法平均復(fù)雜分析PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1離散數(shù)學(xué)算法平均復(fù)雜分析離散數(shù)學(xué)算法平均復(fù)雜分析2第1頁(yè)/共33頁(yè)3i=056281734i=056281734i=056281734i=126581734i=126581734i=221586734i=221586734i=32138675421346758第2頁(yè)/共33頁(yè)4nnTn )(!1前提前提: :假設(shè)輸入服從均勻分布假設(shè)輸入服從均勻分布 n:n個(gè)數(shù)的排列個(gè)數(shù)的排列, T( n):輸入為輸入為 n時(shí)算法的計(jì)算時(shí)間時(shí)算法的計(jì)算時(shí)間, ,Tn: :輸入規(guī)模為輸入規(guī)模為n 時(shí)的平均計(jì)算時(shí)間時(shí)的平均計(jì)算時(shí)間. . n, P( n)=1/n!, Tn=ET( n)=設(shè)軸值設(shè)軸值x是第是

2、第i個(gè)小的數(shù)個(gè)小的數(shù), 有有 T( n)= T( i 1)+ T( n i)+O(n).第3頁(yè)/共33頁(yè)5niiniiniiiTnTinninTTiin1111111)!1()(1)!()()(11 niiniininTnTnTn111)!1()!1()( 表示對(duì)表示對(duì)n 1中取中取n i的所有的所有排列求和排列求和第4頁(yè)/共33頁(yè)6)(2)(!)!1(2)(!11111nOTnnOTnnTnTniiniinnn 又又T0=0, 得得 Tn=O(nlogn) 第5頁(yè)/共33頁(yè)7算法算法13.7 桶排序算法桶排序算法輸入輸入0,1)上的上的n個(gè)數(shù)個(gè)數(shù)Bucketsort(A)1. n|A|2.

3、for i1 to n do3. 把把Ai插入表插入表4. for i0 to n 1 do5. 用插入排序算法對(duì)表用插入排序算法對(duì)表Bi進(jìn)行排序進(jìn)行排序6. 依次連接表依次連接表B0, B1, Bn 1inAB第6頁(yè)/共33頁(yè)8102)(niimO102)(niimEO前提前提:A1,A2,An相互獨(dú)立且都相互獨(dú)立且都U0,1)T(A):對(duì)輸入對(duì)輸入A的計(jì)算時(shí)間的計(jì)算時(shí)間, mi :桶桶Bi中數(shù)的個(gè)數(shù)中數(shù)的個(gè)數(shù), 0in 1, m0+ m1+ mn 1=n, Tn:輸入規(guī)模為輸入規(guī)模為n時(shí)的平均計(jì)算時(shí)間時(shí)的平均計(jì)算時(shí)間. T(A)=O(n)+ Tn=ET(A)=O(n)+第7頁(yè)/共33頁(yè)9)

4、.(12)(12)(.12)(,11)(, 1)(,1,102nOnnOnOnOnOTnmEnmDmEnnBmniniiii第8頁(yè)/共33頁(yè)10第9頁(yè)/共33頁(yè)11第10頁(yè)/共33頁(yè)12第11頁(yè)/共33頁(yè)13j12345678NEXTDATAKK1K2K3K4K5K6K7K8h(K)31141004j12345678NEXTK1DATANILj12345678NEXTK1K2DATANILNILj12345678NEXTK1K2K3DATANIL3NILj12345678NEXTK1 K2K3K4DATANIL3NIL NILj12345678NEXTK1 K2K3K4K5DATANIL35N

5、IL NILj12345678NEXTK1 K2K3K4K5K6DATANIL35NIL NIL NILj12345678NEXTK1 K2K3K4K5K6K7DATANIL35NIL NIL7NILj12345678NEXTK1 K2K3K4K5K6K7K8DATANIL358NIL7NILNILi01234T i01234T1 i01234T21 i01234T21 i01234T214 i01234T214 i01234T6214 i01234T6214 第12頁(yè)/共33頁(yè)14niiDATAhKhXi, 2 , 1, 0),()(, 1否則否則若若簡(jiǎn)單均勻散列函數(shù)簡(jiǎn)單均勻散列函數(shù): K,

6、 h(K)服從服從0,1,m 1上的均勻分上的均勻分布布, 且關(guān)鍵碼的取值相互獨(dú)立且關(guān)鍵碼的取值相互獨(dú)立.插入的平均時(shí)間復(fù)雜度插入的平均時(shí)間復(fù)雜度設(shè)設(shè)DATA中已有中已有n個(gè)數(shù)據(jù)個(gè)數(shù)據(jù),關(guān)鍵碼關(guān)鍵碼K不在不在DATA中中.設(shè)循環(huán)次設(shè)循環(huán)次數(shù)為數(shù)為M, M等于比較等于比較DATAi=K的次數(shù)的次數(shù). 令令 相互獨(dú)立且都服從參數(shù)相互獨(dú)立且都服從參數(shù)1/m的的0-1分布分布, 于是于是 M=X1+X2+XnB(n,1/m), E(M)=n/m第13頁(yè)/共33頁(yè)15)1()211()1(1)1()11(111111 OmnOinmOOmiOnTnTnininiin插入的平均時(shí)間復(fù)雜度為插入的平均時(shí)間復(fù)

7、雜度為 Tn=O(1+),其中其中=n/m稱(chēng)作稱(chēng)作負(fù)載因子負(fù)載因子 檢索的平均時(shí)間復(fù)雜度檢索的平均時(shí)間復(fù)雜度第14頁(yè)/共33頁(yè)16 K, 產(chǎn)生一個(gè)搜索序列產(chǎn)生一個(gè)搜索序列hK,0, hK,1, hK,m 1,它它是是0,1, m 1的一個(gè)排列的一個(gè)排列.第15頁(yè)/共33頁(yè)17!)!1(1)!1(miminiiMP前提前提: :假設(shè)搜索序列服從均勻分布假設(shè)搜索序列服從均勻分布, 即即 K, 序列序列hK,0, hK,1, hK,m 1為為0,1, m 1每一個(gè)排列的可能性相每一個(gè)排列的可能性相等等. 插入的平均時(shí)間復(fù)雜度插入的平均時(shí)間復(fù)雜度設(shè)插入設(shè)插入K所用的循環(huán)次數(shù)為所用的循環(huán)次數(shù)為M. 對(duì)對(duì)

8、 i(1in), Mi 當(dāng)且當(dāng)且僅當(dāng)僅當(dāng) Th(K,0),Th(K,1),Th(K,i 2)已被占用已被占用. 當(dāng)當(dāng)1in時(shí)時(shí),第16頁(yè)/共33頁(yè)1811)()2()1()2()1(iimnimmminnn 1)(kkXPXE當(dāng)當(dāng)i n時(shí)時(shí), PMi=0.定理定理 設(shè)隨機(jī)變量設(shè)隨機(jī)變量X取非負(fù)整數(shù)值且數(shù)學(xué)期望存在取非負(fù)整數(shù)值且數(shù)學(xué)期望存在, 則則得得,11)(11 iiME 11OTn第17頁(yè)/共33頁(yè)19檢索的平均時(shí)間復(fù)雜度檢索的平均時(shí)間復(fù)雜度mnmjniniinjOimmOnTnT11011)1(1)(11 11ln1ln111111nmmdxxjmnmmnmj 11ln1OTn得得m-n

9、m-n+1mxy1第18頁(yè)/共33頁(yè)20第19頁(yè)/共33頁(yè)21第20頁(yè)/共33頁(yè)22第21頁(yè)/共33頁(yè)23這是拉斯維加斯算法這是拉斯維加斯算法第22頁(yè)/共33頁(yè)24, 0, 1否否則則與與若若比比較較jiijaaX 111111ninijijninijijpXE記記Tn:n個(gè)數(shù)排序的平均計(jì)算時(shí)間個(gè)數(shù)排序的平均計(jì)算時(shí)間. ai:A中秩為中秩為i的元素的元素.令令 P Xij =1=pij, 1ijn.平均比較次數(shù)為平均比較次數(shù)為比較比較ai,aj (ij) 軸值軸值首次在首次在ai,aj中時(shí)恰好為中時(shí)恰好為ai或或aj記記B:主元第一次在主元第一次在ai,ai+1,aj中中, D:主元恰好是主元

10、恰好是ai或或aj第23頁(yè)/共33頁(yè)251212|ijmijmBDPpij,212121112111111nniinkninijninijijnHkijp 設(shè)設(shè)B發(fā)生時(shí)發(fā)生時(shí)組內(nèi)有組內(nèi)有m個(gè)數(shù)個(gè)數(shù), mj i+1,得得 Tn=O(nlogn) 其中其中Hn是第是第n個(gè)調(diào)和數(shù)個(gè)調(diào)和數(shù)第24頁(yè)/共33頁(yè)26問(wèn)題問(wèn)題: 任給一個(gè)任給一個(gè)n元多項(xiàng)式元多項(xiàng)式p(x1, x2, xn), 問(wèn)問(wèn)p(x1, x2, xn)是否恒為零是否恒為零? a1, a2, an是是p 0的的見(jiàn)證見(jiàn)證: p(a1, a2, an)0 引理引理13.1 設(shè)設(shè)p(x1, x2, xn)是域是域F上的上的n元元d 次多項(xiàng)式次多項(xiàng)

11、式, S是是F的一個(gè)有窮子集的一個(gè)有窮子集. 隨機(jī)變量隨機(jī)變量a1, a2, an相互獨(dú)立且都服從相互獨(dú)立且都服從S上的均勻分布上的均勻分布, 則則 P p(a1, a2, an)=0p 0d/|S|.證證 對(duì)對(duì)n作歸納證明作歸納證明. 當(dāng)當(dāng)n=1時(shí)結(jié)論成立時(shí)結(jié)論成立. .假設(shè)當(dāng)假設(shè)當(dāng)n 1時(shí)結(jié)論成立時(shí)結(jié)論成立, 設(shè)設(shè)p(x1, x2, xn) 0, 則則第25頁(yè)/共33頁(yè)27, ),(),(02121kiniinxxqxxxxp. ),()(02111kiniiaaqxxp,SdSkSkd其中其中0kd, qk( x2, xn) 0, 其次數(shù)其次數(shù)d k. 記記于是于是, P p(a1, a

12、2, an)=0|p 0=Pqk(a2,an)=0|qk 0Pp1(a1)=0|qk(a2,an)=0,qk 0+Pqk(a2,an)0|qk 0Pp1(a1)=0|qk(a2,an)0, qk 0Pqk(a2,an)=0|qk 0+Pp1(a1)=0|qk(a2,an)0 得證結(jié)論對(duì)得證結(jié)論對(duì)n也成立也成立.第26頁(yè)/共33頁(yè)28算法是單側(cè)錯(cuò)誤的算法是單側(cè)錯(cuò)誤的: :當(dāng)當(dāng)p0時(shí)時(shí),必返回必返回“p0”, 結(jié)論正確結(jié)論正確; 當(dāng)當(dāng)p 0時(shí)時(shí), 可能返回可能返回“p 0”, 也可能返回也可能返回“p0”.算法的錯(cuò)誤概率不超過(guò)算法的錯(cuò)誤概率不超過(guò)1/2.算法算法13.11 多項(xiàng)式恒零測(cè)試隨機(jī)算法多

13、項(xiàng)式恒零測(cè)試隨機(jī)算法Poly(p)p是一個(gè)是一個(gè)n元元d 次多項(xiàng)式次多項(xiàng)式1. 產(chǎn)生產(chǎn)生n個(gè)相互獨(dú)立的個(gè)相互獨(dú)立的0,1,2d 1上均勻分布的隨機(jī)數(shù)上均勻分布的隨機(jī)數(shù) a1, a2, an2. if p(a1, a2, an)0 then 返回返回“p 0”3. else 返回返回“p0” 第27頁(yè)/共33頁(yè)29算法是單側(cè)錯(cuò)誤的算法是單側(cè)錯(cuò)誤的, ,錯(cuò)誤概率錯(cuò)誤概率 2 k算法算法13.12 改進(jìn)的多項(xiàng)式恒零測(cè)試隨機(jī)算法改進(jìn)的多項(xiàng)式恒零測(cè)試隨機(jī)算法Repeated Poly(p,k)p是一個(gè)是一個(gè)n元元d 次多項(xiàng)式次多項(xiàng)式, k是一個(gè)正整數(shù)是一個(gè)正整數(shù)1. for i1 to k do2. i

14、f Poly(p)=“p 0” then 輸出輸出“p 0”, 結(jié)束結(jié)束;3. 輸出輸出“p0”. 第28頁(yè)/共33頁(yè)30, 1mod2nasi, 1mod2 nnaskn的合數(shù)見(jiàn)證的合數(shù)見(jiàn)證1: an 1 1(mod n), 1an 1引理引理13.2 設(shè)設(shè)p是素?cái)?shù)是素?cái)?shù), 1an 1. 如果如果a2k1(mod p), 則則 ak1(mod p) 或或 ak 1(mod p). n的合數(shù)見(jiàn)證的合數(shù)見(jiàn)證2: 設(shè)設(shè)n是奇數(shù)是奇數(shù), n 1=2ts, 1an 1, 其中其中s是奇是奇數(shù)數(shù). 如果存在如果存在0kt, 使得使得 k+1it 且且 則則n是合數(shù)是合數(shù).第29頁(yè)/共33頁(yè)31第30頁(yè)/共33頁(yè)32算法算法13.13 素?cái)?shù)測(cè)試素?cái)?shù)測(cè)試Primality(n)1. if n是偶數(shù)是偶數(shù)n2 then return 合數(shù)合數(shù)2. if n=2 then return 素?cái)?shù)素?cái)?shù)3. if n=1 then return n=14. 計(jì)算計(jì)算 t 和和 s 使得使得n 1=2ts, 其中其中s是奇數(shù)是奇