実行時間はO（nlogn）と一致しますか？

Question

Iは、最初に、私はO（nlogn）

Collections.sort（アレイ、新しい SortingObjectsWithProbabilityField（））を有し、ソート方法を使用したことクラス（貪欲なストラテジ）に書かれています。

、その後、私は別のnためO(h)とh here is the tree height.

を取るbinary search treeのinsertメソッドを使用し、実行している時間は次のようになります。私は理由高めるために正しくないと思い

n,running time 
17,515428 
33,783340 
65,540572 
129,1285080 
257,2052216 
513,4299709 

nでは、実行時間はほとんど増加するはずです。

このメソッドは、実行中の時間がかかります。

Exponent = -1; 



for(int n = 2;n<1000;n+=Math.pow(2,exponent){ 

    for (int j = 1; j <= 3; j++) { 
       Random rand = new Random(); 
       for (int i = 0; i < n; i++) { 
        Element e = new Element(rand.nextInt(100) + 1, rand.nextInt(100) + 1, 0); 
        for (int k = 0; k < i; k++) { 
         if (e.getDigit() == randList.get(k).getDigit()) { 
          e.setDigit(e.getDigit() + 1); 
         } 
        } 
        randList.add(e); 
       } 
       double sum = 0.0; 

       for (int i = 0; i < randList.size(); i++) { 
        sum += randList.get(i).getProbability(); 
       } 
       for (Element i : randList) { 
        i.setProbability(i.getProbability()/sum); 
       } 
       //Get time. 
       long t2 = System.nanoTime(); 
       GreedyVersion greedy = new GreedyVersion((ArrayList<Element>) randList); 
       long t3 = System.nanoTime(); 
       timeForGreedy = timeForGreedy + t3 - t2; 
      } 
      System.out.println(n + "," + "," + timeForGreedy/3); 
      exponent++; 
      } 

おかげ

Answer 1

あなたのデータはnlognの順番に似ています。カーブがのほぼの線形であることに注意してください。大きな値のnの場合、lognはかなり小さくなります。たとえば、n = 513の最大値の場合、lognは9.003です。

より正確なタイミングを達成する方法があります。これにより、曲線がデータポイントによくフィットするようになります。たとえば、タイマーの誤差を滑らかにするために、ランダムな入力のサンプルを大量に取るなど（可能ならば少なくとも10,100にする）、データセットごとに複数の繰り返しを実行する（5は受け入れ可能な数値です）などです。単一のスタート/ストップタイマーを使用して、同じnのすべての繰り返しを実行してから、ランの数で除算して、より正確なデータポイントを得ることができます。最初にすべてのデータセットを生成し、すべて保存してからすべて実行するようにしてください。

2の累乗でnをサンプリングするのに適しています。実際に影響を与えるのではなく、1を減算して正確に2の累乗にしたい場合があります。

set terminal png 
set output 'graph.png' 
set xrange [0:5000000] 
set yrange [0:600] 
f1(x) = a1*x*log(x)/log(2) 
a1 = 1000 
plot 'time.dat' title 'Actual runtimes', \ 
    a1*x*log(x)/log(2) title 'Fitted curve: O(nlogn) 
fit f1(x) 'time.dat' via a1 

Answer 2

それが実行されている時代に漸近複雑に関連することは容易ではありません。サンプルが非常に小さいときは、タイミングに影響を与えることがたくさんあります。あなたは（33、17でK回例えばK倍など）のインスタンスごとに、あなたのアルゴリズムK回実行する必要があり、より正確なタイミングを持っていると

（例えばK = 100）のサンプル点として平均時間を取るために

それは正しいようだと言った。 nlog（n）とタイミングをプロットすることができます。異なるスケールにもかかわらず、同様に成長しています。まだあまりにも小さなサンプルポイントは確かに...