算法分析作业答案.doc

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 low<high then
2. 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 ]。