算法分析习题参考答案第三章

算法分析习题参考答案第三章

第三章 分治算法习题

1、编写程序实现归并算法和快速排序算法

参见后附程序

2、用长为100、200、300、400、500、600、700、800、900、1000的10个数组的排列来统计这两种算法的时间复杂性。

有些同学用的微秒us

用s可能需要把上面的长度改为10000，……，100000，都可以

大部分的结果是快速排序算法要比归并算法快一些。

3、讨论归并排序算法的空间复杂性。

解析：归并排序由分解与合并两部分组成，如果用S(n)表示归并排序所用的空间。 则由

MergeSort(low, mid) //将第一子数组排序 S(n/2)

MergeSort(mid+1, high) //将第二子数组排序 S(n/2)

Merge(low, mid, high) //归并两个已经排序的子数组 O(n) 2n

则

S(n) max{S(n/2),O(n)}

S(n) S(n/2) O(n)

递归推导得

nnnS(n) S() O(n) S() O() O(n)242

nnn S(1) O(k) O(k 1) O() O(n) 222

S(1) O(2n)

O(n)

又由存储数组长度为n ，则有 S(n) O(n)

因此，空间复杂度为O(n)。

4、说明算法PartSelect的时间复杂性为O(n)

证明：

（1）当r 7时，假设数组A中元素互不相同。由于每个具有7个元素的数组的中间值u是该数组中的第4小元素，因此数组中至少有4个元素不大于u， n/7 个中间值中至少有 n/7 /2 个不大于这些中间值的中间值v。因此，在数组A中至少有

算法分析习题参考答案第三章

4 n/7 /2 n/7 2

个元素不大于v。换句话说，A中至多有

n 2 n/7 n 2(n/7 e/7)

个元素大于v。同理，至多有512n ,(0 e 6) 77512n 个元素小于v。这样，以v为划分元素，产生的新数77

51251211 n。 组至多有n 个元素。当n 24时，n 777714

另一方面，在整个执行过程中，递归调用Select函数一次，涉及规模为n/7，而下一次循

11环Loop涉及的数组规模为n。程序中其他执行步的时间复杂度至多是n的倍数cn，用14

T(n)表示算法在数组长度为n的时间复杂度，则当n 24时，有递归关系

111T(n) T(n) T(n) cn 714

用数学归纳法可以证明，T(n) 14cn。所以时间复杂度是O(n)。

（2）当r 3时，使用上述方法进行分析，可知在进行划分后数组A中有至多225n n336个元素。而递归关系为T(n) T(n) T(n) cn。若通过归纳法证明出有T(n) kcn的形式，用数学归纳法可以证明，T(n) 28cn。所以时间复杂度是O(n)。

提示：假定数组中的元素各不相同，且第一次划分时划分元素v是第i小元素的概率为1/n。因为Partition中的case语句所要求的时间都是O(n)，所以，存在常数c，使得算法PartSelect的平均时间复杂度CA(n)可以表示为

kCA(n) cn 1356k1k ikCA(n i) CA(i 1) n1 i kk i n

令R(n) max(CA(n)),取C R(1),试证明R(n) 4cn。 kk

证明：令CA(n)表示n个元素的数组A中寻找第k小元素的平均时间复杂度，因k

Partition(0,n-1)的时间复杂度是O(n)，故存在常数c，使得

kCA(n) cn 1k ik( CA(n i) CA(i 1)) n1 i kk i n

k令R(n) max(CA(n)),且等式在k kn时成立。则 k

算法分析习题参考答案第三章

R(n) cn 1() n

以下用第二数学归纳法证明R(n) 4cn。

当n 1时，不妨设R(1) 4c

当n 2时，R(2) 2c 11R(1) 2c 4c 4c成立。 22

对于一般的n，设对所有小于n的自然数R(n) 4cn成立，则 R(n) cn 1(R(n 1) R(n kn 1)) (R(kn) R(kn 1) R(n 1))n

4c cn ((n 1) (n kn 1)) (kn (n 1))n

4c(k 1)(2n kn)(n kn)(kn n 1) cn (n )n22

4c2n2 3n cn (kn (n 1)kn ) n2

4cn 12n2 3n cn ( () )n22

3n2 4n 1 cn cn

cn c(3n 3)

4cn

得证。

归并排序的 C++语言描述

#include<iostream.h>

template<class T>void MergeSort(T a[],int left,int right); template<class T>void Merge(T c[],T d[], int l,int m,int r); template<class T>void Copy(T a[],T b[],int l,int r);

void main()

{

int const n(5);

int a[n];

cout<<"Input "<<n<<"numbers please:";

for(int i=0;i<n;i++)

cin>>a[i];

//for(int j=0;j<n;j++)

//b[j]=a[j];

MergeSort(a,0,n-1);

cout<<"The sorted array is"<<endl;

算法分析习题参考答案第三章

for(i=0;i<n;i++)

cout<<a[i];

cout<<endl;

}

template<class T>

void MergeSort(T a[],int left,int right) // {

if(left<right)

{

int i=(left+right)/2;

T *b=new T[];

MergeSort(a,left,i);

MergeSort(a,i+1,right); Merge(a,b,left,i,right); Copy(a,b,left,right); }

template<class T>

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(c[i]<=c[j])d[k++]=c[i++]; else d[k++]=c[j++];

}

if(i>m)

{

for(int q=j;q<=r;q++) d[k++]=c[q]; }

else

for(int q=i;q<=m;q++) d[k++]=c[q]; }

template<class T>

void Copy(T a[],T b[], int l,int r)

{

for(int i=l;i<=r;i++)

a[i]=b[i];

算法分析习题参考答案第三章

}

快速排序的 C++语言描述

#include<iostream.h>

template<class T>void QuickSort(T a[],int p,int r); template<class T>int Partition(T a[],int p,int r); void main()

{

int const n(5);

int a[n];

cout<<"Input "<<n<<"numbers please:"; for(int i=0;i …… 此处隐藏：1590字，全部文档内容请下载后查看。喜欢就下载吧 ……