CLRS-Chapter2

2.1-1:略

2.1-2：把伪代码里面的大于改成小于即可

2.1-3:

   

2.1-4:

      add(a,b,c)

        ct<-0

        for i<-1 to n-1

          do c[i]<-a[i]+b[i]+ct

          if(c[i]>1)

          c[i]<-c[i]-1

          ct=1;

        if(c[n]>1)

        c[n]<-c[n]-1

        c[n+1]<-1

2.2-1:

 

 

2.2-2:

 

2.2-3:

 

 

2.2-4:略

 

 

2.3-1:略

2.3-2:框架代码为：

      while(i

      {

       ...

       }

      while(i

      while(j

2.3-3:

      当n=2时T(2)=2=2lg2,满足条件

      假设对于n/2成立，即T(n/2)=n/2lg(n/2)，则：

      T(n)=2T(n/2)+n=nlg(n/2)+n=nlgn-n+n=nlgn,符合假设，故T(n)=nlgn成立

2.3-4：

      n=1时，T(n)=O(1),否则

      T(n)=T(n-1)+O(n)

2.3-5:

      迭代版本：

      public static int binary_search(int A[],int v,int low,int high)
 {
   while(low<=high)
   {
    int mid=(low+high)/2;
    if(v==A[mid])
     return mid;
    if(v    {
     high=mid-1;
    }
    else
     low=mid+1;
   }
   return -1;
 }

    递归版本：

public static int binary_search1(int A[],int v,int low,int high)
 {
  if(low>high)
   return -1;
  int mid=(low+high)/2;
  if(v==A[mid])
   return mid;
  if(v>A[mid])
   return binary_search1(A,v,mid+1,high);
  else
   return binary_search1(A,v,low,mid+1);
 }

时间分析：对于输入为n的运行时间可写为：T(n)=T(n/2)+O(1);由主定理可知时间复杂度为O(nlgn).

2.3-6:不能，虽然二分查找可以把查找时间从O(n)缩短为O(lgn)，但是平均插入的时间还是O(n)不变，故总的时间复杂度仍然是O(nlgn)

 

2.3-7:步骤如下：

      1）对S集合排序,如果有多个相同元素，只保留一个；

      2)对于S集合的每个值，构造S'{z：z=x-y}y属于S，并按照步骤一的操作来操作S’集合

      3）对S和S'集合进行merge操作，若操作后的集合有相同元素，则可以判断出存在着有两个其和等于x的元素。证明略。

 

思考题：

2-1：

   a）最坏情况下，对每一个长度为k的子列表进行排序的时间为O(k^2),故总时间为O(k^2*n/k)=O(nk)

   b)对n/k个子列表两两进行合并，总共需要lg(n/k)，而每一步的合并都需要O(n)的时间，故总时间为O(nlg(n/k));

   c)k=O(lgn)

   d)略

2-2：

   a)我们需要显示A'的元素是A的元素的排列。

   b)略

   c)略

   d)O(n^2)，与插入排序的最差运行时间相同

2-3:

   a)O(n)

   b)朴素的算法如果一项一项算的话，时间复杂度为O(n^2)

   c)略

   d)略

2-4：

   a)(8 6),(2 1),(3 1),(8 1),(6 1)

   b)逆序的数组，他包含有1+2+。。。+n-1=n(n-1)/2个逆序对。

   c)两者是一个数量级，因为对于每一个逆序对，必然存在相关的比较和数据移动

   d)java代码如下：

 public static int countInversions(int a[],int p,int r)
 {
  int inversion=0;
  if(p  {
   int q=(p+r)/2;
   inversion+=countInversions(a,p,q);
   inversion+=countInversions(a,q+1,r);
   inversion+=inversionMerge(a,p,q,r);
  }
  return inversion;
 }
 private static int inversionMerge(int[] a, int p, int q, int r) {
  // TODO Auto-generated method stub
  //System.out.println(p+" "+q+" "+r);
  int n1=q-p+1;
  int n2=r-q;
  int[] L=new int[n1+2];
  int[] R=new int[n2+2];
  for(int i=1;i<=n1;i++)
   L[i]=a[p+i-1];
  for(int i=1;i<=n2;i++)
   R[i]=a[q+i];
  L[n1+1]=Integer.MAX_VALUE;
  R[n2+1]=Integer.MAX_VALUE;
  int inversions=0;
  int i=1,j=1;
  boolean counted=false;
  for(int k=p;k<=r;k++)
  {
   //System.out.println(i+" "+j+" "+n1+" "+n2);
   if(counted==false&&L[i]>R[j])
   {
    inversions=inversions+n1-i+1;
    counted=true;
   }
   if(L[i]<=R[j])
   {
    a[k]=L[i];
    i++;
   }
   else
   {
    a[k]=R[j];
    j++;
    counted=false;
   }
  }
  return inversions;
 }

注意：数组下标从1开始。。。

 

 

 

 

 

 

 

阅读(440) | 评论(0) | 转发(0) |

0

上一篇：Java EE启示录

下一篇：SRM463总结