Javaコードのbig-O時間の複雑さを計算するためのツールですか？

Question

Javaソフトウェアの時間複雑度（大きなO表記）に関する質問があります。それを迅速に計算したりテストしたりする方法がありますか（または私にとってそれを計算できるウェブサイトは歓迎されるでしょう）。例えば、私は、次のコードスニペットのためにそれをチェックし、可能性も改善したい：

int dcount = 24423567; 
     int a = 0; 
     if (dcount == 0){ 
      a = 1; 
     } 

     String ds = Integer.toString(dcount); 
     String[] sa = ds.split("(?<=.)"); 
     HashSet hs = new HashSet(); 
     Collections.addAll(hs, sa); 
     a = hs.size(); 
     if (dcount < 0) 
      a--; 

     System.out.println(a); 

Answer 1

@emoryが指摘したように、任意のピースのビッグOの時間複雑度を決定するために証明可能不可能ですコードは自動的に（証明はHalting Problemからの還元です）。しかし、いくつかの異なる入力でそれを実行することによって、経験的にコードの複雑さを測定しようとすることができるツールがあります。このようなツールの1つが、Goldsmith、Aiken、Wilkersonの論文「Measuring Experimental Computational Complexity」に記載されています。これは、プログラムのランタイムと入力サイズの間の回帰を試みることによって機能します。 trend-profと呼ばれるこのツールは、オンラインで入手できます。

希望すると便利です。

Answer 2

私は誰かの宿題を解決するかもしれませんが、質問は正気解決のために物乞いされました...数に明確な数字を数える

は、単にいくつかの簡単な算術演算を何文字列、セットまたは正規表現を必要としません。

以下の方法は、（N =入力の桁数）と一定の間隔O（N）時間で実行される：負の数は、この仕事を作る

int distinctDigits(int num) { 
    if (num == 0) { 
    return 1; 
    } 

    boolean[] digits = new boolean[10]; 

    while (num > 0) { 
    digits[num % 10] = true; 
    num /= 10; 
    } 

    int count = 0; 
    for (boolean digit : digits) { 
    if (digit) { 
     count++; 
    } 
    } 

    return count; 
} 

がリーダにexericseとして残されます。 ）