算法分析作业答案

6.6、设A[1…n]是一个由n个整数组成的数组，x为一整数。给出一个分治算法，找出x在 A中出现的频度，即x在A中出现的次数。你的算法的时间复杂度是什么？

输入：整数数组A[1…n]，整数x

输出：x在数组A[1…n]中出现的频度

Frequence(A,1,h,x)

过程 Frequence (A,low,high,x)

1. if high – low = 0

2. if A[low] = x return 1

3. else return 0;

4. end if

5. if high – low > 0

6. mid ← ( low+high)/2

7. Return Frequence(A,low,mid,x)+Frequence(A,low+1,high,x)

8. end if

T(n)=O(n)

6.16、考虑以下MERGESORT的修改算法。我们将算法应用到输入数组A[1…n]上并不断递 归调用，直到子问题的规模变得相对很小，即m或是小于m。此时转向INSERTSOR，

并将其运用到小的那部分，因此修改算法的第一个检验条件将变为

if (high – low + 1 <= m) then INSERTSORT(A[low...high])

在修改算法的运行时间仍不变的前提下，用n来表示m的最大值因是多少？为简单起

见，可以假定n是2的幂。

输入：待排序数组A[low,...high]

输出：A[low…high]按非降序排列

MERGESORT(A[low…high])

过程 MERGESORT(A, low,high)

1.if low2. if (high – low + 1 <= m) then INSERTSORT(A,low,high)

3. else

4. mid←(low+high)/2

5. MERGESORT(A, low, mid)

6. MERGESORT(A, mid+1, high)

7. MERGE(A, low, mid, high)

8. end if

9. end if

M<=2log n +1

6.38、解释当输入已按降序排列时算法QUICKSORT的行为，可以假定输入元素是互不相同 的。

算法QUICKSORT是这样的：

1、设置两个变量start、end，排序开始的时候：start=1，end=N；

2、以第一个数组元素作为关键数据，赋值给pivot，即 pivot=arry[1]；

3、从end开始向前搜索，即由后开始向前搜索（end--），找到第一个小于pivot的值 arry[end]，并与arry[start]交换,即swat(arry,start,end)；

4、从start开始向后搜索，即由前开始向后搜索（start++），找到第一个大于pivot

的arry[start]，与arry[end]交换,即swat(arry,start,end);

5、重复第3、4步，直到 start==end，这个时候arry[start]=arry[end]=pivot，

而pivot的位置就是其在整个数组中正确的位置；

6、通过递归，将问题规模不断分解。将pivot两边分成两个数组继续求新的pivot，

最后解出问题。

但是当输入已按降序排列时，假定输入元素有n个且互不相同。那么第一次执行第5步时，arry[1]和arry[n]交换。然后通过递归，出现arry[2]和arry[n-1]交换arry[3]和arry[n-2]交换.....如果n是偶数，最后一次交换的是arry[n/2]和arry[n/2 +1]；如果n是奇数，最后一次交换的是arry[（n-1）/2]和arry[（n+1）/2 ]。