空间合并算法的时间复杂度怎样计算

Question

           设子数组a[0:k]和a[k+1:n-1]已排好序(0≤k≤n-1)。试设计一个合并这两个子树组为排好序的树组a[0:n-1]的算法。要求算法在最坏的情况下所用的计算时间为O(n)，且只用到O(1)的辅助空间。
 
算法如下：
            public static void merge(Comparable []a, int k,int n)
{      int i=0,j=k+1,d=0; 
            while ((i<=n-1)&&(j<=n-1))
            if(a[i]<a[j]) i++;  
            else   {     d++; 
                            for(int p=j+1;p<=n-1;p++) 
                               if(a[p]<=a[i]) d++;
                            int t=a[i]; 
                            while(d>0)  
                             {  a[i]=a[j];
                                for(q=j;q>i+1;q--)  a[q]=a[q-1];
                                --d;++i;++j; 
                              }
                            a[i]=t; i++;   
                      }
}能不能给出具体一点的时间复杂度分析过程，谢谢！

Answer 1

拉链法 int[] a = { 5, 7, 9, 21, 29, 79, 89 };
int[] b = { 3, 5, 11, 25, 35, 78, 100, 110, 112 };
int[] c = new int[a.length + b.length];
int bi = 0;
int ai = 0;
for (int i = 0; i < c.length; i++) {
if(ai==a.length){
c[i]=b[bi];
bi++;
continue;
}
if(bi==b.length){
c[i]=a[ai];
ai++;
continue;
}
if (a[ai] < b[bi]) {
c[i] = a[ai];
ai++;
} else {
c[i] = b[bi];
bi++;
}
}
for (int i : c) {
System.out.println(i);
}时间复杂度为O(n)，空间复杂度O(1)。
替换成你需要的参数就OK了

Answer 2

楼主的时间复杂度为O(n2)    n2是n的平方
空间复杂度为O(n)