分時排序算法的時間複雜度是多少？

-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

分時排序算法的時間複雜度是多少？

回答

相關問題