程序4-1-2递归求最大最小值算法伪代码 MaxMin(i,j,fmax,fmin)//A[l:n]是n个元素的数组,参数i,j /是整数,1≤i≤j≤n,使用该过程将数组A[i:j中的最大最小元 //分别赋给fmax和fmin。 global n, A[l: n]: integer i, j: fmax=fmin=A[i]:\\子数组A[i:j中只有一个元素 elseif i=j-1then\\子数组A[i:j中只有两个元素 if Ali]<ALj then fmin=A[i]: fmax=ALj else fmin=A[j]: fmax=ALi] endif else mid(i+j)/2」;\\子数组A[i:j中的元素多于两个 MaxMin(i, mid, gmax, gmin) MaxMin(mid+l, j, hmax, hmin); fmax=max(gmax, hmax) fmin=main(gmin, hmin) endif end Maxmin 如果用T(n)来表示 MaxMin所用的元素比较数,则上述递归算法导出一个 递归关系式: T(n)={1 2 4.1.2 2)+T(n/2b 当n是2的方幂时,设n=2,有 2(2T(n/4)+2) =47(n/4)+4+2 2=7(2) 2k-1+2k-2程序 4-1-2 递归求最大最小值算法伪代码 MaxMin（i,j,fmax,fmin）//A[1:n]是 n 个元素的数组，参数 i，j //是整数，1≤i≤j≤n，使用该过程将数组 A[i:j]中的最大最小元 //分别赋给 fmax 和 fmin。 global n, A[1:n]; integer i, j; if i=j then fmax=fmin=A[i]; \\子数组 A[i:j]中只有一个元素 elseif i=j-1 then \\子数组 A[i:j]中只有两个元素 if A[i]<A[j] then fmin=A[i]; fmax=A[j]； else fmin=A[j]; fmax=A[i]; endif else mid=(i+j)/2; \\子数组 A[i:j]中的元素多于两个 MaxMin(i, mid, gmax, gmin); MaxMin(mid+1, j, hmax, hmin); fmax=max(gmax, hmax)； fmin=main(gmin, hmin)； endif end Maxmin 如果用 T(n)来表示 MaxMin 所用的元素比较数，则上述递归算法导出一个 递归关系式：        + + > = = = ( / 2 ) ( / 2 ) 2 2 1 2 0 1 ( ) T n T n n n n T n (4.1.2) 当n是2 的方幂时，设 k n = 2 ，有 3 / 2 2 2 2 2 2 (2) 2 4 ( / 4) 4 2 2(2 ( / 4) 2) 2 ( ) 2 ( / 2) 2 1 1 1 1 = − = + − = + = + + = + + = + − ≤ ≤ − − ∑ n T T n T n T n T n k k i k k i L