离散数学算法平均复杂分析PPT学习教案

1、会计学1离散数学算法平均复杂分析离散数学算法平均复杂分析2第1页/共33页3i=056281734i=056281734i=056281734i=126581734i=126581734i=221586734i=221586734i=32138675421346758第2页/共33页4nnTn )(!1前提前提: :假设输入服从均匀分布假设输入服从均匀分布 n:n个数的排列个数的排列, T( n):输入为输入为 n时算法的计算时间时算法的计算时间, ,Tn: :输入规模为输入规模为n 时的平均计算时间时的平均计算时间. . n, P( n)=1/n!, Tn=ET( n)=设轴值设轴值x是第是

2、第i个小的数个小的数, 有有 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个数个数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中数的个数中数的个数, 0in 1, m0+ m1+ mn 1=n, Tn:输入规模为输入规模为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否则否则若若简单均匀散列函数简单均匀散列函数: K,

6、 h(K)服从服从0,1,m 1上的均匀分上的均匀分布布, 且关键码的取值相互独立且关键码的取值相互独立.插入的平均时间复杂度插入的平均时间复杂度设设DATA中已有中已有n个数据个数据,关键码关键码K不在不在DATA中中.设循环次设循环次数为数为M, M等于比较等于比较DATAi=K的次数的次数. 令令 相互独立且都服从参数相互独立且都服从参数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, 产生一个搜索序列产生一个搜索序列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所用的循环次数为所用的循环次数为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取非负整数值且数学期望存在取非负整数值且数学期望存在, 则则得得,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个数排序的平均计算时间个数排序的平均计算时间. ai:A中秩为中秩为i的元素的元素.令令 P Xij =1=pij, 1ijn.平均比较次数为平均比较次数为比较比较ai,aj (ij) 轴值轴值首次在首次在ai,aj中时恰好为中时恰好为ai或或aj记记B:主元第一次在主元第一次在ai,ai+1,aj中中, D:主元恰好是主元

10、恰好是ai或或aj第23页/共33页251212|ijmijmBDPpij,212121112111111nniinkninijninijijnHkijp 设设B发生时发生时组内有组内有m个数个数, mj i+1,得得 Tn=O(nlogn) 其中其中Hn是第是第n个调和数个调和数第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, 其次数其次数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. 产生产生n个相互独立的个相互独立的0,1,2d 1上均匀分布的随机数上均匀分布的随机数 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是一个正整数是一个正整数1. for i1 to k do2. i

14、f Poly(p)=“p 0” then 输出输出“p 0”, 结束结束;3. 输出输出“p0”. 第28页/共33页30, 1mod2nasi, 1mod2 nnaskn的合数见证的合数见证1: an 1 1(mod n), 1an 1引理引理13.2 设设p是素数是素数, 1an 1. 如果如果a2k1(mod p), 则则 ak1(mod p) 或或 ak 1(mod p). n的合数见证的合数见证2: 设设n是奇数是奇数, n 1=2ts, 1an 1, 其中其中s是奇是奇数数. 如果存在如果存在0kt, 使得使得 k+1it 且且 则则n是合数是合数.第29页/共33页31第30页/共33页32算法算法13.13 素数测试素数测试Primality(n)1. if n是偶数是偶数n2 then return 合数合数2. if n=2 then return 素数素数3. if n=1 then return n=14. 计算计算 t 和和 s 使得使得n 1=2ts, 其中其中s是奇数是奇