java - 运行时间是否与 O(nlogn) 匹配？

Question

我写了一个类(贪心策略)，起初我使用了 O(nlogn) 的排序方法

Collections.sort(array, new SortingObjectsWithProbabilityField());

然后我使用了 二叉搜索树 的插入方法，它采用 O(h) 和 h 这里是树的高度。

对于不同的n，运行时间为:

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 的幂，而不是它会产生任何实际影响。

作为引用，这里是 gnuplot用于生成绘图的脚本:

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