算法第四章PPT.ppt

首先调用QUICKSORT(1,7) //low=1,high=7 if 17 then { j=8; call PARTITION(1, 8); call QUICKSORT(low, j-1) call QUICKSORT(j+1, high) } end QUICKSORT 4.5 快速分类 快速分类实例分析过程 等PARTITION(1, 8)调用结束后,返回参数j的值,才能执行递归调用 PARTITION(m, p) //m=1, p=8 t=A[m]=5; i=m=1; loop(第1次) loop i++ until A[i]≥t ; i=3 loop p-- until A[p]≤t ; p=6 if (ip) then A[i]?? A[p]; A[1] A[2] A[3] A[4] A[5] A[6] A[7] 5 3 9 2 7 1 8 A[1] A[2] A[3] A[4] A[5] A[6] A[7] 5 3 1 2 7 9 8 过程MAXMIN的时间复杂度 MAXMIN的元素比较次数 当n=2k (k是某个正整数)时，有T(n)=3n/2-2 T(n)= 2T(n/2)+2 = 2(2T(n/4)+2)+2 = 4T(n/4)+4+2 …… = 2k-1T(2)+( 2k-1 +2k-2+…+22+2 ) =2k-1+2k-2 =3n/2-2 与直接算法的比较次数2(n-1)相比，比较次数减少了25 %。 0 n=1 1 n=2 T(n)= T( n/2 )+ T( n/2 )+2 n2 4.3 找最大和最小元素 可以证明: 任何一种以比较为基础的找最大和最小元素的算法，其元素比较次数的下界为 3n/2 -2 但是不代表该算法最优，理由如下： MAXMIN算法分析 MAXMIN所需的存储空间比直接算法多 4.3 找最大和最小元素 给出n个元素，则MAXMIN算法有 logn +1级的递归，每次递归都需要保存i, j, fmax, fmin和返回地址5个值 直接算法需要空间为: n+3, 用n个位置存放数组A，还有i, max, min三个变量需要存储 元素A(i)和A(j)的比较与i和j的比较时间相差不大时，过程MAXMIN不可取。 设MAXMIN的频率计数为C(n)，n=2k , k为整数, 当n2时, 有: C(n)=5n/2-3 4.3 找最大和最小元素 C(n)= 2C(n/2)+3 = 2(2C(n/4)+3)+3 = 4C(n/4)+6+3 …… = 2k-1C(2)+3*( 2k-2 +2k-3+…+22+21+20 ) =2k+3*(2k-1-1) =2k+3*2k-1-3 =5n/2-3 2 n=2 C(n)= 2C( n/2 )+ 3 n2 直接算法的比较次数为2(n-1), 加上实现for循环 需要的比较次数, 则为3(n-1), 虽然3(n-1)略大于 5n/2-3, 但MAXMIN算法还有递归所带来的时间 开销, 这种情况下直接算法要快一些 结论: 如果数组A的元素之间的比较远比整型变量的比较代价昂贵，分治算法略优于直接比较算法。 4.3 找最大和最小元素 一般方法(插入法) For j←2 to n do 将A(j)放入已分类A(1:j-1) 4.4 归并分类 问题描述: 给定一个含有n个元素的集合， 把它们按一定的次序分类(如非降次序) procedure INSERTIONSORT(A, n) A[0] ← -∞; for j ← 2 to n do { item ← A[j]; i ← j-1; while ( itemA[i]) do { A[i+1] ← A[i]; i ← i-1; } A[i+1] ← item; } end INSERTIONSORT 插入分类算法描述 数组元素的移动 插入排好序的值 可能执行0~j次(j=2,3…n) 最好情况Ω(n) 最坏情况的计算时间：2+…+n=(n(n+1)/2)-1=Θ(n2) 用item保存当前元素值 4.4 归并分类 4.4 归并分类 A[0] A