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

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

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

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

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

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

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

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

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

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

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

11、式, S是是F的一個有窮子集的一個有窮子集. 隨機變量隨機變量a1, a2, an相互獨立且都服從相互獨立且都服從S上的均勻分布上的均勻分布, 則則 P p(a1, a2, an)=0p 0d/|S|.證證 對對n作歸納證明作歸納證明. 當當n=1時結論成立時結論成立. .假設當假設當n 1時結論成立時結論成立, 設設p(x1, x2, xn) 0, 則則第25頁/共33頁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 得證結論對得證結論對n也成立也成立.第26頁/共33頁28算法是單側錯誤的算法是單側錯誤的: :當當p0時時,必返回必返回“p0”, 結論正確結論正確; 當當p 0時時, 可能返回可能返回“p 0”, 也可能返回也可能返回“p0”.算法的錯誤概率不超過算法的錯誤概率不超過1/2.算法算法13.11 多項式恒零測試隨機算法多

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

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