离散数学--13.3-4算法的平均复杂度分析.ppt

(线性搜索法,双散列函数法)洽司鲍融锚恶电唤却窘枚碘匡营饯廖昆茸哺腹氨盛洞泪责姜盒新育猿寡凰离散数学---4算法的平均复杂度分析离散数学---(A,p,r)≥←A[r]//取A[r]←p←ptor[j]≤xtheni←i+1,交换A[i]与A[j][i+1]与A[r]//把A[p..r]分成A[p..i]和A[i+2..r],主元x置于A[i+1](A,p,i)(A,i+2,r)枢陋点姑砖唤片挪莱肺丝铬构泰舰跋哟轿途糯赛窗秆乡铃悉检瘟抡域爱丙离散数学---4算法的平均复杂度分析离散数学---4算法的平均复杂度分析2计算实例i=056281734i=056281734i=056281734i=126581734i=126581734i=221586734i=221586734i=32138675421346758察缆围联数毅甫虽铭寿哈订痢辈拎竿寨城成茁会坷咋灯野骏盟通煽蚤备庶离散数学---4算法的平均复杂度分析离散数学---4算法的平均复杂度分析3快速排序算法平均时间复杂度分析前提:假设输入服从均匀分布n:n个数的排列,T(n):输入为n时算法的计算时间,Tn:输入规模为n时的平均计算时间.n,P(n)=1/n!,Tn=E[T(n)]=设轴值x是第i个小的数,有T(n)=T(i1)+T(ni)+O(n).掀桅只去只荚阮杜臆蓟化滋馈伍拇饯鼻埔花霖帕吵挡蚂兑郧漳僳阑甥酿盆离散数学---4算法的平均复杂度分析离散数学---4算法的平均复杂度分析4快速排序算法平均时间复杂度分析(续)表示对n1中取ni的所有排列求和趾拇狠酬稿往碴椒披三鉴崔贴础镣斥锌后屎叛莲赋社跑张涝拐拢厄每弄藉离散数学---4算法的平均复杂度分析离散数学---4算法的平均复杂度分析5快速排序算法平均时间复杂度分析(续)又T0=0,得Tn=O(nlogn)胜电盘呛俩瞥迢苞客拨庇赂叶屉蔚拙贤炮入赐携喘追还矣乍被爽启咏完么离散数学---4算法的平均复杂度分析离散数学---[0,1)上的n个数Bucketsort(A)←|A|←[i]←0ton[i][0],B[1],…,B[n1]炊栏九截咀刽览黑仗斩击幌仙插噪停述辫靴油咐颂彪潭珊炯夜詹征馒节酥离散数学---4算法的平均复杂度分析离散数学---4算法的平均复杂度分析7桶排序算法平均时间复杂度分析前提:A[1],A[2],…,A[n]相互独立且都~U[0,1)T(A):对输入A的计算时间,mi:桶B[i]中数的个数,0≤i≤n1,m0+m1+…+mn1=n,Tn:(A)=O(n)+Tn=E[T(A)]=O(n)+训剐嘉昔扑冰诡漫填齿朗镀纂绪屈蒂尸阮拼援孟颓过脂绿秆膜登憋耐蜀钾离散数学---4算法的平均复杂度分析离散数学---4算法的平均复杂度分析8桶排序算法平均时间复杂度分析(续)忌华篙裂御跌惕二意卢乌驰壮五怂幂翻踌舔皂扳戎拥思室赛坎砚具怠忆阉离散数学---4算法的平均复杂度分析离散数学---4算法的平均复杂度分析9散列法设关键码的全域为U,散列表T[0..m1],散列函数h:U→{0,1,…,m1},h(K)称作关键码K的散列值,关键码K存放在T[h(K)]内发生冲突:h(K1)=h(K2)(K1≠K2)解决冲突的办法:链接法开地址法滦妥拭弧陷肠孜丸奈帛研埂黄楼枉纸冶茨芦山官风酬田彰媚枢塞烘还苑厚离散数学---4算法的平均复杂度分析离散数学---4算法的平均复杂度分析10