分时排序算法的时间复杂度是多少？

-4

我在Java中开发了一个时间共享相似算法来执行整数排序。该程序如下所示，但是，我不知道如何计算算法的时间复杂度。任何人都可以告诉我最糟糕的情况是什么？分时排序算法的时间复杂度是多少？

import java.util.ArrayList; 


public class TimeSharingSort { 

public static void main(String[] args){ 
    int[] array = {10,9,8,7,6,5,4,3,2,1,0}; 
    int[] count = new int[array.length]; 
    int i,j=0; 
    ArrayList<Integer> a = new ArrayList<Integer>(array.length); 
    while(a.size()!=array.length){ 
     for(i=0;i<array.length-j;i++){ 
      if(count[i]<array[i]){ 
       count[i]++; 
       //System.out.println("count["+i+"]="+count[i]+"   array["+i+"]="+array[i]); 
      } 
      else if(count[i]==array[i]){ 
       a.add(array[i]); 
       j++; 
      } 
     } 
    } 
    for(i=0;i<a.size();i++){ 
     System.out.print(a.get(i)+" "); 
    } 
} 

}

来源

2017-07-15 Syntax-Tax

复杂度为O（n^2）。原因： - 程序的核心部分在一段时间内使用for循环，这会导致O（n^2）。

来源

2017-07-15 07:49:42

这是不完全正确的。 while循环并不依赖于n，而是依赖于数组中的数字之和。例如，排序{10000,90000}比排序{1,0}慢100000倍。 – Henry

是的，绝对，我同意。但我也在学习。但先生，根据你，它应该是什么复杂的呢？ –

如果's'是数组中所有数字的总和，则努力是'O（s + n）'。 – Henry

分时排序算法的时间复杂度是多少？

回答

相关问题