3三分治算法习题参考答案

《3三分治算法习题参考答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章分治算法习题1、编写程序实现归并算法和快速排序算法参见后附程序2、用长为100、200、300、400、500、600、700、800、900、1000的10个数组的排列来统计这两种算法的时间复杂性。有些同学用的微秒us用s可能需要把上面的长度改为10000，……，100000，都可以大部分的结果是快速排序算法要比归并算法快一些。3、讨论归并排序算法的空间复杂性。解析：归并排序由分解与合并两部分组成，如果用表示归并排序所用的空间。则由MergeSort(low,mid)//将第一子数组排序MergeSort(mid+1,hi

2、gh)//将第二子数组排序Merge(low,mid,high)//归并两个已经排序的子数组则递归推导得又由存储数组长度为，则有因此，空间复杂度为。4、说明算法PartSelect的时间复杂性为证明：提示：假定数组中的元素各不相同，且第一次划分时划分元素是第小元素的概率为。因为Partition中的case语句所要求的时间都是，所以，存在常数，使得算法PartSelect的平均时间复杂度可以表示为令取试证明。证明：令表示n个元素的数组A中寻找第k小元素的平均时间复杂度，因的时间复杂度是，故存在常数c，使得算法PartSelect的

3、平均时间复杂度可以表示为令且不妨设等式在时成立，则满足以下用第二数学归纳法证明。取当时，取cC/4,则当时，成立。对于一般的n，设对所有小于n的自然数成立，则得证。证明：（1）当时，假设数组A中元素互不相同。由于每个具有7个元素的数组的中间值u是该数组中的第4小元素，因此数组中至少有4个元素不大于u，个中间值中至少有个不大于这些中间值的中间值v。因此，在数组A中至少有个元素不大于v。换句话说，A中至多有个元素大于v。同理，至多有个元素小于v。这样，以v为划分元素，产生的新数组至多有个元素。当时，。另一方面，在整个执行过程中，递归调

4、用Select函数一次，涉及规模为，而下一次循环Loop涉及的数组规模为。程序中其他执行步的时间复杂度至多是n的倍数，用表示算法在数组长度为n的时间复杂度，则当时，有递归关系用数学归纳法可以证明，。所以时间复杂度是。（2）当时，使用上述方法进行分析，可知在进行划分后数组A中有至多个元素。而递归关系为。若通过归纳法证明出有的形式，用数学归纳法可以证明，。所以时间复杂度是。归并排序的C++语言描述#includetemplatevoidMergeSort(Ta[],intleft,intrigh

5、t);templatevoidMerge(Tc[],Td[],intl,intm,intr);templatevoidCopy(Ta[],Tb[],intl,intr);voidmain(){intconstn(5);inta[n];cout<<"Input"<>a[i];//for(intj=0;j

6、ayis"<voidMergeSort(Ta[],intleft,intright)//{if(leftvoidMerge(T

7、c[],Td[],intl,intm,intr){inti=l;intj=m+1;intk=l;while((i<=m)&&(j<=r)){if(c[i]<=c[j])d[k++]=c[i++];elsed[k++]=c[j++];}if(i>m){for(intq=j;q<=r;q++)d[k++]=c[q];}elsefor(intq=i;q<=m;q++)d[k++]=c[q];}templatevoidCopy(Ta[],Tb[],intl,intr){for(inti=l;i<=r;i++)a[i]=b[

8、i];}快速排序的C++语言描述#includetemplatevoidQuickSort(Ta[],intp,intr);templateintPartition(Ta[],intp,int