算法分析作业答案.doc

《算法分析作业答案.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、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.ifhigh–low=02.ifA[low]=xreturn13.elsereturn0;4.endif5.ifhigh–low>06.mid←ë(low+high)/2û7.ReturnFrequence(A,low

2、,mid,x)+Frequence(A,low+1,high,x)8.endifT(n)=O(n)6.16、考虑以下MERGESORT的修改算法。我们将算法应用到输入数组A[1…n]上并不断递归调用，直到子问题的规模变得相对很小，即m或是小于m。此时转向INSERTSOR，并将其运用到小的那部分，因此修改算法的第一个检验条件将变为if(high–low+1<=m)thenINSERTSORT(A[low...high])在修改算法的运行时间仍不变的前提下，用n来表示m的最大值因是多少？为简单起见，可以假定n是2的幂。输入：待排序

3、数组A[low,...high]输出：A[low…high]按非降序排列MERGESORT(A[low…high])过程MERGESORT(A,low,high)1.iflow

4、解释当输入已按降序排列时算法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++），找到

5、第一个大于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

6、-1]交换arry[3]和arry[n-2]交换.....如果n是偶数，最后一次交换的是arry[n/2]和arry[n/2+1]；如果n是奇数，最后一次交换的是arry[（n-1）/2]和arry[（n+1）/2]。