标签: 算法设计与分析

  一个长度为 L（L≥1）的升序序列 S，处在第 L/2个位置的数称为 S 的中位数。例如，若序列 S1=（11,13,15,17,19），则 S1 的中位数是 15，两个序列的中位数是含它 们所有元素的升序序列的中位数。例如，若 S2=（2,4,6,8,20），则 S1 和 S2 的中位数 是 11。现在有两个等长升序序列 A 和 B，试设计一个在时间和空间两方面都尽可能高效 的算法，找出两个序列 A 和 B 的中位数。要求：  （1）给出算法的基本设计思想。  （2）根据设计思想，采用 C 或 C++或 JAVA 语言描述算法，关键之处给出注释。  （3）说明你所设计算法的时间复杂度和空间复杂度。    解答： int middle_number(int A ,int n){     int la=0,lb=0,ha=n-1,hb=n-1,ma,mb;     while(la=halb=hb){         ma=(la+ha)/2;         mb=(lb+hb)/2;         if(A ==B )             return A ;         if(A B ){             la=ma+1;             hb=mb-1;         }         else{             ha=ma-1;             lb=mb+1;         }     }     return A B ?A :B ; }  

  设将n(n,1)个整数存放到一维数组R中，试设计一个在时间和空间两方面尽可能有效的算法，将R中保有的序列循环左移P(0﹤P﹤n)个位置，即将R中的数据由(X0 X1 ……Xn-1)变换为(Xp Xp+1 ……Xn-1 X0 X1 ……Xp-1)要求： 　　(1)给出算法的基本设计思想。 　　(2)根据设计思想，采用C或C++或JAVA语言表述算法，关键之处给出注释。 　　(3)说明你所设计算法的时间复杂度和空间复杂度   分析：题目本身不是很难，但是要设计出最高效的算法还不那么容易。直观感觉，时间复杂度为O(n),空间复杂度为O(1),想了好久，想出了这种方法，但是不知道怎么证明，高手赐教！   （1）当n%p==0时，可以做p*(n/p)次搬运，具体的说就是每一趟搬运的是等价类，做p次。 （2）当n%p!=0时，做n次a =a ;但是，我不知道怎么证明？   代码如下： void move_p_steps(int a ;             for(j=n-1-i-p;0=j;j-=p)                 a =a ;             a =temp;         }     }     else{         j=0;         temp=a ;         for(i=0;in;i++){             temp1=a ;             a =temp;             temp=temp1;             j=(j+p)%n;         }     } }