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

13.3 算法的平均复杂度分析 13.3.1 排序算法 快速排序算法 桶排序算法 13.3.2 散列表的检索和插入 散列函数 链接法 开地址法(线性有哪些信誉好的足球投注网站法,双散列函数法) 快速排序算法 算法13.6 快速排序算法 Quicksort(A,p,r) 1. if p≥r then return A 2. x←A[r] //取A[r]作为轴值 3. i←p?1 4. for j←p to r?1 do 5. if A[j]≤x then i←i+1, 交换A[i]与A[j] 6. 交换A[i+1]与A[r] //把A[p..r]分成A[p..i]和A[i+2..r], 主元x置于A[i+1] 7. Quicksort(A,p,i) 8. Quicksort(A,i+2,r) 计算实例 快速排序算法平均时间复杂度分析 快速排序算法平均时间复杂度分析(续) 快速排序算法平均时间复杂度分析(续) 桶排序算法 桶排序算法平均时间复杂度分析 桶排序算法平均时间复杂度分析(续) 散列法 设关键码的全域为U, 散列表T[0..m?1], 散列函数h:U→{0,1,…,m?1}, h(K)称作关键码K的散列值, 关键码K存放在T[h(K)]内 发生冲突: h(K1) = h(K2) (K1≠K2) 解决冲突的办法: 链接法 开地址法 链接法 链接法(续) 算法13.8 链式散列表的检索和插入算法 Chained Hash(K,n) 1. i←h(K) 2. if T[i]=Λ then n←n+1, T[i]←n, 转8 //建一个新的链表 3 i←T[i] 4. if i=N+1 then 溢出, 结束 /表已满, 查找失败 5. if DATA[i]=K then 输出i, 结束 /查找成功 6. if NEXT[i]=NIL then n←n+1, NEXT[i]←n, 转8 //插入K 7. i←NEXT[i], 转4 8. if n≤N then DATA[n]←K, NEXT[n]←NIL 计算实例 算法13.8的平均时间复杂度 算法13.8的平均时间复杂度(续) 开地址法 算法13.9 开地址散列表的检索和插入算法 Open Adress Hash(T,K) 1. for i←0 to m?1 do 2. j←h(K,i) 3. if T[j]=K then 输出j, 结束 //查找成功 4. if T[j]=0 then T[j]←K, 结束 //插入K, 设所有K≠0 5. 溢出. //表已满, 查找失败 算法13.9的平均时间复杂度 算法13.9的平均时间复杂度(续) 算法13.9的平均时间复杂度(续) 常用的开地址法 线性有哪些信誉好的足球投注网站法 有哪些信誉好的足球投注网站序列为 h(K,i)=(h1(K)+ic) mod m, i=0,1,…,m?1, 其中h1:U→{0,1,…,m?1}是一个散列函数, c是一个与m互 素的正整数. 双散列函数法 有哪些信誉好的足球投注网站序列为 h(K,i)=(h1(K)+ih2(K)) mod m, i=0,1,…,m?1, 其中h1和h2是2个散列函数, h2(K)与m互素. 13.4 随机算法 13.4.1 随机快速排序算法 随机算法 单侧错误和双侧错误 蒙特卡罗法和拉斯维加斯法 13.4.2 多项式恒零测试 13.4.3 素数测试 随机算法 随机算法(概率算法):带有随机操作的算法 随机操作:产生随机数并根据随机数决定下一步的运算 拉斯维加斯(Las Vegas)算法:计算结果总是正确的, 但允 许不作结论或拒绝回答 蒙特卡罗(Monte Carlo)算法:可能给出错误的结果 单侧错误:可能把是说成非, 但不可能把非说成是 双侧错误:既可能把是说成非, 也可能把非说成是 随机算法的性能分析 平均计算时间:相对于随机数的分布,而与输入分布无关 错误(拒绝回答的)概率 随机快速排序算法 算法13.10 随机快速排序算法 Random QuickSort(A) 1. 设n=|A|, if n=1 then return A 2. 产生一个{1,2,…,n}上均匀随机数k 3. 令y←A[k], 以y作轴值将A划分为A1和A2 4. Random QuickSort(A1) 5. Random QuickSort(A2) 6. 按下述顺序排列A的元素: A1, y, A