算法MINMAX 输入：n 个整数元素的数组A[1…n]，n 为2 的幂。 输出：（x，y），A 中的最大元素和最小元素。 1. minmax（1, n） 过程 minmax(low, high) 1. if high – low = 1 then 2. if A[low] < A[high] then return (A[low], A[high]) 3. else return (A[high], A[low]) 4. end if 5. else 6. mid ← ⌊(low+high)/2⌋ 7. (x1, y1) ← minmax(low, mid) 8. (x2, y2) ← minmax(mid+1, high) 9. x ← min(x1, x2) 10. y ← max(y1, y2) 11. return (x, y) 12. end if （1）假设n=2k，请分析该算法的时间复杂度（5 分）； （2）当输入为4、1、3、8、9、5、7，以上算法能否得到正确结果？给出理由（5 分）； （3）尝试将算法改成对于任意输入规模大小为n 时都成立（5 分）； （4）尝试分析修改后算法的时间复杂度（5 分）。

（1）该算法的时间复杂度为O(n)，其中n为数组A的元素个数。因为每次递归都会将问题规模缩小为原来的一半，所以递归层数为log n，每层的时间复杂度为O(1)，所以总时间复杂度为O(n log n)。

（2）该算法能够得到正确结果。在第一次调用minmax函数时，low=1，high=7，mid=4，所以分成了两个子问题minmax(1, 4)和minmax(5, 7)。在第一个子问题中，low=1，high=4，mid=2，所以又分成了minmax(1, 2)和minmax(3, 4)。在最后的minmax(1, 2)中，high-low=1，所以直接返回(A[low], A[high])=(4,1)。同理可以得到minmax(3, 4)的结果为(3,8)。在第二个子问题中，low=5，high=7，mid=6，所以又分成了minmax(5, 6)和minmax(7, 7)。在minmax(5, 6)中，high-low=1，直接返回(5,9)。最后在minmax(1,4)和minmax(5,7)的结果中，x的最小值为1，y的最大值为9，因此算法得到的结果为(1,9)。

（3）将算法改写为对于任意输入规模大小为n都成立的形式：

minmax(low, high, A)
1. if high – low = 1 then
2.     if A[low] < A[high] then 
3.         return (A[low], A[high])
4.     else 
5.         return (A[high], A[low])
6.     end if
7. else
8.     mid ← ⌊(low+high)/2⌋
9.     (x1, y1) ← minmax(low, mid, A)
10.    (x2, y2) ← minmax(mid+1, high, A)
11.    x ← min(x1, x2)
12.    y ← max(y1, y2)
13.    return (x, y)
14. end if

（4）修改后的算法仍然具有与原算法相同的时间复杂度，即O(n log n)。因为每次递归仍然会将问题规模缩小为原来的一半，递归层数为log n，每层的时间复杂度为O(1)，所以总时间复杂度为O(n log n)。