关于输出最小的k个的数的时间复杂度

bjutslg

用到的是关于快排中的思想，可以基于Partition函数来解决这个问题，如果基于数字的地K个数字来调整，使得比第k个小的数字都在数组的左边，大的都在K的右边
代码

1. void GetLeastNumbers（int * input,int n,int * oupt,int k)
   
2. {
   
3.           if(intput==NULL||output==NULL||k>n||n<0||k<=0)
   
4.                  return ;
   
5.           int start=0;
   
6.           int end =n-1;
   
7.           int index=Partition(input,n,statrt,end);
   
8.          while(index!=k-1)
   
9.          {
   
10.                 if(index>k-1)
    
11.                 {
    
12.                         end = index-1;
    
13.                         index = Partition(input,n,start,end);
    
14.                 }
    
15.                 else
    
16.                 {
    
17.                          start=index+1;
    
18.                          index=Partition(input,n,start,end);
    
19.                 }
    
20.          }
    
21.          for(int i=0;i<k;i++)
    
22.               output[i]=input[i];
    
23. }

复制代码

这个时间复杂度O(n)是怎么算出来的

jwj070524

严格的证明在算法导论里面是有的。
第一遍分割：遍历N个元素，分成两组，时间是O(N)，如果左边那组的数量少于K，进入右边继续分割；如果左边数量多于K个，则仍旧在左边分割；如果刚好分割点是第K个元素，那么算法结束。
第二遍分割：最多遍历N-1个（由于上一次分割一定产生两组，因此每组元素最大个数不会超过N-1个），判断同上
第三遍分割：最多遍历N-2个（同上）...
所以算法的最差时间复杂度是N+(N-1)+(N-2)+...+(N-K+1) = K*N - K(K-1)/2 = O(K*N -K^2) = O(K(N-K))
如果K比较大的话，比如N/2，那么最差时间复杂度就是O(N^2)

jwj070524