java – 运行时间与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++;
            }

谢谢