Exercises
2.1-1 略。
2.1-2 略。
2.1-3
C/C++ Code:
int Search(int A[],int v){
for(int i=0;i++;i<=n) //n表示数组中元素的个数
if(A[i]==v)
return i;
return NULL;
}
循环不变式：
初始化：i=0，只有一个元素A[0],如果v=A[0],则返回0，否则返回NULL,算法显然是正确的。
保持： 若算法对A[0...i]是正确的，当数组增加到A[0...i+1]时，只是多做了一次比较，显然也是正确的。
终止： 如果经历了A.length次查找能找到必然会返回一个值，若没有成功，则会返回NULL。算法一定会返回一个返回值，要么成功返回等于v元素的下标，要么返回NULL，所以算法是正确的。
2.1-4
形式化描述： 数组A存放n位二进制整数的各位数值，数组B同样存放了另一个整数。通过二进制的加法进行运算，将结果保存在具有n+1个元素的数组C中。
C/C++ Code：
void Binary_Add(int a[],int b[],int c[]){
c[0]=0;
for(int i=0;i<=n;i++){ //n表示A，B数组中元素的个数
c[i+1]=(a[i]+b[i]+c[i])/2;
c[i]=a[i]^b[i]^c[i];
}
}
2.2-1 略。
2.2-2
C/C++ Code：
void Selection_Sort(int a[]){
int key,i,j,index;
for(j=0;j<=n-1;j++){
key=a[j];
index=j;
for(i=j+1;i<=n;i++) //n表示数组中含有的元素个数
if(a[i]<key){
key=a[i];
index=i;
}
a[index]=a[j];
a[j]=key;
}
}
循环不变式：A[0...i-1]的数据都是排好序的。
当你进行到n-1个元素的时候，后面就剩第n个元素了，注定是最大的，所以不用对其进行排序。
无论是最好情况还是最坏情况，需要比较的次数都是一定的，所以时间复杂度都是Θ(n)。
2.2-3
平均需要检查n/2个元素。
最坏需要检查n个元素。
最坏情况和平均情况都应是Θ(n)。
2.2-4
控制算法的输入的数据，使其发生最好的情况。
2.3-1 略。
2.3-2
C/C++ Code：
void Merge(int A[],int p,int k, int q){
int R[MAX],L[MAX];
int i,j,l;
for(i=0;i<=k-p;i++)
L[i]=A[p+i];
for(j=0;j<=q-k-1;j++)
R[j]=A[k+j+1];
i=j=0;
for(l=p;l<=q;l++){
if(i>k-p||j>q-k-1) //其中任意一个数组中所有元素都被复制回A时，即终止循环
break;
if(L[i]>=R[j])
A[l]=R[j++];
else
A[l]=L[i++];
}
// 将另一个数组中的剩余元素复制回A
for(;i<=k-p;i++,l++)
A[l]=L[i];
for(;j<=q-k-1;j++,l++)
A[l]=R[j];
}
void Merge_Sort(int a[],int p,int q){
if(p<q){
int k=(p+q)/2;
Merge_Sort(a,p,k);
Merge_Sort(a,k+1,q);
Merge(a,p,k,q);
}
}
2.3-3
1.当n=2时，即k=1时，可知 = 2 = 2lg 2$)
.
2.假设当k>2时， = 2{
m{T}}left( {{2^{{
m{k}} - 1}}}
ight) + {2^{
m{k}}} = {2^{
m{k}}}lg {2^{
m{k}}} = {
m{k}} cdot {2^{
m{k}}}$)
成立，则可以证明 = 2{
m{T}}left( {{2^{
m{k}}}}
ight) + {2^{{
m{k}} + 1}} = left( {{
m{k}} + 1}
ight){2^{{
m{k}} + 1}} = {2^{{
m{k}} + 1}}lg {
m{k}} + 1$)
。
3.因此，当k>=1时，且n是2的幂时， = {
m{n}}lg {
m{n}}$)
。
2.3-4
n=1或2时，T(n)=1;
n>2时 ， = {
m{T}}left( {{
m{n}} - 1}
ight) + {
m{Theta }}left( {
m{n}}
ight)$)
。
2.3-5
C/C++ Code:
int Binary_Search(int a[],int m,int n,int v){
if(v>a[n]||v<a[m]||m==n) //n代表数组中的元素数量
return NULL;
else{
int k;
k=(m+n)/2;
if(v==a[k])
return k;
else if(v>a[k])
Binary_Search(a,k+1,n,v);
else if(v<a[k])
Binary_Search(a,m,k,v);
}
}
该算法运行时间由比较的次数决定，最坏情况时，需要经过lgn次中点比较，最后要么找到返回该值，要么返回NULL,所以时间复杂度为Θ(lgn)。
2.3-6
不会的，虽然改用二分查找法的查找时间变为了lgn，但最后还是需要移动j-1个元素，所以算法时间复杂度无法改进到Θ(nlgn)。
2.3-7
1.构建一个辅助集合S‘，其中的元素为用x依次减去S中的元素。
2.对S和S'分别进行排序。
3.删除S中重复的元素，S’同样。
4合并S和S‘，只要有相同的元素出现两次，其必然在相邻的位置，则可以确定S中存在两个其和刚好为x的元素。
Thinking Problems
2-1
a.最坏情况下插入排序 排序一个长度为k的子表，所需时间为$)
，所以编辑n/k个子表所需时间为Θ(nk)。
b.在归并排序中，每一层的带价都是n，共有n/k个叶子节点，所以递归树的高度是lg(n/k),即lg(n/k)+1层，所以可以在Θ(nlg(n/k))内合并这些子表。
c.若要使修改后的算法与归并排序有相同的运行时间，即Θ(nlg(n/k)+nk)=Θ(nlgn)。那么k必须小于lgn。
d.k尽量大但要小于插入排序快于归并排序的临界值。
2-2
a.A'中排序好的元素就是A'中的元素，此时A‘中的元素即为A中的元素。
b.循环不变式：A[j]是j到n中的最小值，
初始化：j=n，A[n]必然是n到n中的最小值。
保持：对于循环不变式可知，A[j...n]是已经排好序的，且A[j]是其最小值，那么只需要比较A[j]和A[j-1]，就可以使A[j-1]是A[j-1...n]的最小值。
终止：当j=i时终止此时A[i]也就是A[i...n]的最小值，此时A‘即为A中的元素。
c.循环不变式：A[1...i-1]就是A[1...n]中的i-1个最小值，且已经排好序。
初始化：i=1时，子数组为空，所以循环不变式成立。
保持：若A[1...i-1]都是A[i...n]的排好序的i-1个最小值，那么A[i]即是剩下数组元素中的最小值，且A[1...i]是排好序的。
终止：i=n时循环终止，此时A[1...n-1]都是A[1...n]中的n-1个最小值，因此A[1...n]是排好序的，且其中元素就是原A[1...n]中的元素。
d.最坏运行时间：$)
，与插入排序相同。
2-3
a.Θ(n)。
b.C/C++ Code：
int Multinomial(int a[],int n,int x){
int sum=a[0];
for(int i=1;i<=n;i++){
int xi=1;
for(int j=1;j<=i;j++)
xi=xi*x;
sum+=a[i]*xi;
}
return sum;
}
运行时间为，性能不如霍纳规则。
c.循环不变式终止时有：i=-1，带入即可证得。
d.循环不变式：
初始化：i=n，y[n]=0,循环后有y[n]=a[n]。
保持：对于 0<i<n,循环后有，
。
终止：对于i=-1时终止，此时有} {{{
m{a}}_{{
m{k}} + {
m{i}} + 1}}{{
m{x}}^{
m{k}}}} $)
。
所以上面给出的代码将正确的求出多项式的值。
2-4
a.略。
b.{n,n-1,n-2....3,2,1}这样的数组有最多的逆序对，共有n(n-1)/2个逆序对。
c.稍微修改一下归并排序即可，若当i<j时,L[i]>R[j],逆序对的数量count则加1，最后统计count的值即可，所以时间复杂度同归并排序，即为所求。
（若有错误和不足，欢迎大家积极指正！）