《3 三 分治算法 习题参考答案.doc》由会员分享，可在线阅读，更多相关《3 三 分治算法 习题参考答案.doc（6页珍藏版）》请在金锄头文库上搜索。
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, high) /将第二子数组排序 Merge(low, mid,
2、high) /归并两个已经排序的子数组 则递归推导得又由存储数组长度为 ，则有 因此，空间复杂度为。4、说明算法PartSelect的时间复杂性为证明：提示：假定数组中的元素各不相同，且第一次划分时划分元素是第小元素的概率为。因为Partition中的case语句所要求的时间都是，所以，存在常数，使得算法PartSelect的平均时间复杂度可以表示为令取试证明。证明：令表示n个元素的数组A中寻找第k小元素的平均时间复杂度，因的时间复杂度是，故存在常数c，使得算法PartSelect的平均时间复杂度可以表示为令且不妨设等式在时成立，则满足以下用第二数学归纳法证明。取当时，取cC/4,则当时，成立
3、。对于一般的n，设对所有小于n的自然数成立，则得证。证明：（1）当时，假设数组A中元素互不相同。由于每个具有7个元素的数组的中间值u是该数组中的第4小元素，因此数组中至少有4个元素不大于u，个中间值中至少有个不大于这些中间值的中间值v。因此，在数组A中至少有个元素不大于v。换句话说，A中至多有个元素大于v。同理，至多有个元素小于v。这样，以v为划分元素，产生的新数组至多有个元素。当时，。另一方面，在整个执行过程中，递归调用Select函数一次，涉及规模为，而下一次循环Loop涉及的数组规模为。程序中其他执行步的时间复杂度至多是n的倍数，用表示算法在数组长度为n的时间复杂度，则当时，有递归关系用
4、数学归纳法可以证明，。所以时间复杂度是。（2）当时，使用上述方法进行分析，可知在进行划分后数组A中有至多个元素。而递归关系为。若通过归纳法证明出有的形式，用数学归纳法可以证明，。所以时间复杂度是。归并排序的 C+语言描述 #include templatevoid MergeSort(T a,int left,int right); templatevoid Merge(T c,T d, int l,int m,int r); templatevoid Copy(T a,T b,int l,int r); void main() int const n(5); int an; coutInpu
5、t nnumbers please:; for(int i=0;iai; /for(int j=0;jn;j+) /bj=aj; MergeSort(a,0,n-1); coutThe sorted array isendl; for(i=0;in;i+) coutai; coutendl; template void MergeSort(T a,int left,int right) / if(leftright) int i=(left+right)/2; T *b=new T; MergeSort(a,left,i); MergeSort(a,i+1,right); Merge(a,b,
6、left,i,right); Copy(a,b,left,right); template void Merge(T c,T d,int l,int m,int r) int i=l; int j=m+1; int k=l; while(i=m)&(j=r) if(cim) for(int q=j;q=r;q+) dk+=cq; else for(int q=i;q=m;q+) dk+=cq; template void Copy(T a,T b, int l,int r) for(int i=l;i=r;i+) ai=bi; 快速排序的 C+语言描述 #include templatevoi
7、d QuickSort(T a,int p,int r); templateint Partition(T a,int p,int r); void main() int const n(5); int an; coutInput nnumbers please:; for(int i=0;iai; QuickSort(a,0,n-1); coutThe sorted array isendl; for(i=0;in;i+) coutai ; coutendl; template void QuickSort(T a,int p,int r) if(pr) int q=Partition(a,p,r); QuickSort(a,p,q-1); QuickSort(a,q+1,r); template int Partition(T a,int p,int r) int i=p,j=r+1; T x=ap; while(true) while(a+ix); if(i=j)break; Swap(ai,aj); ap=aj; aj=x; return j; template inline void Swap(T &s,T &t) T temp=s; s=t; t=temp;
