Java TreeSet BigO 的复杂度似乎降低了

Question

我相信 Java TreeSet 有一个平衡树实现，可以快速执行树排序（很像快速排序）。我最近遇到的问题表明它似乎执行了我预期的更多比较。

是否每棵平衡树都像 Java 的 TreeSet 一样执行排序（插入），还是我的性能测试方法有误？

我的代码：

package expri.johnny.treeSortCompTimes;


import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.TreeSet;

public class TreeSetCompTimeTest {
    public static void main(String[] args) {
        int size=1000;
        ArrayList<Integer> ay =new ArrayList<>(size);
        int treeHeight =   (int) (Math.log (size)/Math.log (2));
        System.out.println("tree height: "+treeHeight); 
        System.out.println("when size is "+ size + ",i expected compare tmies are: "+((treeHeight+1)*treeHeight/2)); 

        for(int i =0,l=size-1;i<=l;i++){
            ay.add(i);
        }


        Collections.shuffle(ay);
        System.out.println(ay);
        CountComp cc =new CountComp();
        TreeSet<Integer> ts =new TreeSet<>(cc);
        ts.addAll(ay);
        cc.speakCount();
    }

    private static class CountComp implements Comparator<Integer>{
        int counter =0;
        @Override
        public int compare(Integer o1, Integer o2) {
            this.counter++;
            int df = o1-o2;
            if(df>0){
                return 1;
            }else if(df==0){
                return 0;
            }else{
                return -1;
            }

        }
        public void speakCount(){
            System.out.println("total compared times: "+this.counter); 
            //when size is 100,i expected compare tmies are: 21 
                //total compared times: 545
            //when size is 1000,i expected compare tmies are: 45
                //however, the real total compared times: 8783
        }
    }
}

嗯，这就是我之前的想法：

10 compares for add
10 compares for add
10 compares for add
10 compares for add
10 compares for add
10 ...
10
10
10
10
10
10 -997th , what i thought was 7 
10 -998th  , what i thought  was 8 
10 - 999th , what i thought  was 9
10 - 1000th  , what i thought was 10 
8547

这次笑死我了material，哈哈哈！

Answer 1

假设插入将使用 log(n) 比较，你是正确的。但是你插入 n 元素给我们 n*log(n) 比较。对于 1000 个元素，它给了我们 9965 个比较。

n这里是元素的总数。

你的公式完全错误，我不知道你从哪里得到的。

Answer 2

随着项目的添加，树的深度是动态的。要估计将进行的比较次数，迭代要添加的元素的大小并根据树的大小计算将对每个元素进行的比较次数那时候。

int sum = 0;
for(int i = 1; i <= size; i++){
    sum += (int)Math.ceil(Math.log(i)/Math.log(2));
}
System.out.println(sum);

1000 个元素产生 8987。

Java TreeSet BigO 的复杂度似乎降低了

Java TreeSet BigO complexity seems off

java

treeset

data-structures