离散数学-13.3-4算法的平均复杂度分析.ppt
1,13.3 算法的平均复杂度分析,13.3.1 排序算法快速排序算法桶排序算法 13.3.2 散列表的检索和插入 散列函数链接法开地址法(线性搜索法,双散列函数法),2,快速排序算法,算法13.6 快速排序算法Quicksort(A,p,r)1.if pr then return A2.xAr/取Ar作为轴值3.ip14.for jp to r1 do5.if Ajx then ii+1,交换Ai与Aj6.交换Ai+1与Ar/把Ap.r分成Ap.i和Ai+2.r,主元x置于Ai+17.Quicksort(A,p,i)8.Quicksort(A,i+2,r),3,计算实例,4,快速排序算法平均时间复杂度分析,前提:假设输入服从均匀分布n:n个数的排列,T(n):输入为n时算法的计算时间,Tn:输入规模为n 时的平均计算时间.n,P(n)=1/n!,Tn=ET(n)=设轴值x是第i个小的数,有 T(n)=T(i1)+T(ni)+O(n).,5,快速排序算法平均时间复杂度分析(续),表示对n1中取ni的所有排列求和,6,快速排序算法平均时间复杂度分析(续),又T0=0,得 Tn=O(nlogn),7,桶排序算法,算法13.7 桶排序算法输入0,1)上的n个数Bucketsort(A)1.n|A|2.for i1 to n do3.把Ai插入表4.for i0 to n1 do5.用插入排序算法对表Bi进行排序6.依次连接表B0,B1,Bn1,8,桶排序算法平均时间复杂度分析,前提:A1,A2,An相互独立且都U0,1)T(A):对输入A的计算时间,mi:桶Bi中数的个数,0in1,m0+m1+mn1=n,Tn:输入规模为n时的平均计算时间.T(A)=O(n)+Tn=ET(A)=O(n)+,9,桶排序算法平均时间复杂度分析(续),10,散列法,设关键码的全域为U,散列表T0.m1,散列函数h:U0,1,m1,h(K)称作关键码K的散列值,关键码K存放在Th(K)内发生冲突:h(K1)=h(K2)(K1K2)解决冲突的办法:链接法 开地址法,11,链接法,12,链接法(续),算法13.8 链式散列表的检索和插入算法Chained Hash(K,n)1.ih(K)2.if Ti=then nn+1,Tin,转8/建一个新的链表3 iTi4.if i=N+1 then 溢出,结束/表已满,查找失败5.if DATAi=K then 输出i,结束/查找成功6.if NEXTi=NIL then nn+1,NEXTin,转8/插入K7.iNEXTi,转48.if nN then DATAnK,NEXTnNIL,13,计算实例,14,算法13.8的平均时间复杂度,简单均匀散列函数:K,h(K)服从0,1,m1上的均匀分布,且关键码的取值相互独立.插入的平均时间复杂度设DATA中已有n个数据,关键码K不在DATA中.设循环次数为M,M等于比较DATAi=K的次数.令 相互独立且都服从参数1/m的0-1分布,于是 M=X1+X2+XnB(n,1/m),E(M)=n/m,15,算法13.8的平均时间复杂度(续),插入的平均时间复杂度为 Tn=O(1+),其中=n/m称作负载因子 检索的平均时间复杂度,16,开地址法,算法13.9 开地址散列表的检索和插入算法Open Adress Hash(T,K)1.for i0 to m1 do2.jh(K,i)3.if Tj=K then 输出j,结束/查找成功4.if Tj=0 then TjK,结束/插入K,设所有K05.溢出./表已满,查找失败,K,产生一个搜索序列hK,0,hK,1,hK,m1,它是0,1,m1的一个排列.,17,算法13.9的平均时间复杂度,前提:假设搜索序列服从均匀分布,即K,序列hK,0,hK,1,hK,m1为0,1,m1每一个排列的可能性相等.插入的平均时间复杂度设插入K所用的循环次数为M.对i(1in),Mi 当且仅当 Th(K,0),Th(K,1),Th(K,i2)已被占用.当1in时,18,算法13.9的平均时间复杂度(续),当i n时,PMi=0.定理 设随机变量X取非负整数值且数学期望存在,则,得,19,算法13.9的平均时间复杂度(续),20,常用的开地址法,线性搜索法 搜索序列为 h(K,i)=(h1(K)+ic)mod m,i=0,1,m1,其中h1:U0,1,m1是一个散列函数,c是一个与m互素的正整数.双散列函数法 搜索序列为 h(K,i)=(h1(K)+ih2(K)mod m,i=0,1,m1,其中h1和h2是2个散列函数,h2(K)与m互素.,21,13.4 随机算法,13.4.1 随机快速排序算法随机算法单侧错误和双侧错误蒙特卡罗法和拉斯维加斯法13.4.2 多项式恒零测试 13.4.3 素数测试,22,随机算法,随机算法(概率算法):带有随机操作的算法 随机操作:产生随机数并根据随机数决定下一步的运算拉斯维加斯(Las Vegas)算法:计算结果总是正确的,但允许不作结论或拒绝回答蒙特卡罗(Monte Carlo)算法:可能给出错误的结果单侧错误:可能把是说成非,但不可能把非说成是双侧错误:既可能把是说成非,也可能把非说成是随机算法的性能分析平均计算时间:相对于随机数的分布,而与输入分布无关错误(拒绝回答的)概率,23,随机快速排序算法,算法13.10 随机快速排序算法Random QuickSort(A)1.设n=|A|,if n=1 then return A2.产生一个1,2,n上均匀随机数k3.令yAk,以y作轴值将A划分为A1和A24.Random QuickSort(A1)5.Random QuickSort(A2)6.按下述顺序排列A的元素:A1,y,A2,这是拉斯维加斯算法,24,算法13.10的平均计算时间,记Tn:n个数排序的平均计算时间.ai:A中秩为i的元素.令 P Xij=1=pij,1ijn.平均比较次数为比较ai,aj(ij)轴值首次在ai,aj中时恰好为ai或aj记B:主元第一次在ai,ai+1,aj中,D:主元恰好是ai或aj,25,算法13.10的平均计算时间(续),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 次多项式,S是F的一个有穷子集.随机变量a1,a2,an相互独立且都服从S上的均匀分布,则 P p(a1,a2,an)=0p 0d/|S|.证 对n作归纳证明.当n=1时结论成立.假设当n1时结论成立,设p(x1,x2,xn)0,则,27,引理13.1证明(续),其中0kd,qk(x2,xn)0,其次数dk.记于是,P p(a1,a2,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也成立.,28,多项式恒零测试随机算法,29,多项式恒零测试随机算法(续),算法是单侧错误的,错误概率2k,算法13.12 改进的多项式恒零测试随机算法Repeated Poly(p,k)p是一个n元d 次多项式,k是一个正整数1.for i1 to k do2.if Poly(p)=“p 0”then 输出“p 0”,结束;3.输出“p0”.,30,素数测试,n的合数见证1:an1 1(mod n),1an1引理13.2 设p是素数,1an1.如果a2k1(mod p),则 ak1(mod p)或 ak1(mod p).n的合数见证2:设n是奇数,n1=2ts,1an1,其中s是奇数.如果存在0kt,使得 k+1it 且 则n是合数.,31,引理13.2证明,证 由a2k1(mod p),存在整数d 使得 a2k=dp+1,(ak+1)(ak1)=dp.由于p是素数,必有 p|ak1 或 p|ak+1,得证 ak1(mod p)或 ak1(mod p).,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 使得n1=2ts,其中s是奇数5.产生一个1,2,n1上的均匀随机数a6.for i=0 to t do7.计算bi,33,素数测试随机算法(续),8.if bt1 then return 合数9.if b0=1 then return 素数10.jmax i|bi111.if bj=n1 then return 素数12.else return 合数,算法是单侧错误的.当n是素数时,必返回素数;而当n是合数时,算法不一定返回合数.可以证明,当n是合数时算法返回素数的概率,即错误概率不超过1/2.,
