java - Java 中 TreeSet 方法的计算复杂性

Question

Java 中 TreeSet 方法的计算复杂度是否与 AVLTree 相同？

具体来说，我想知道以下方法的计算复杂度: 1.添加 2.删除 3.首先 4.最后 5.地板 6.更高

方法描述的 Java 文档:http://docs.oracle.com/javase/6/docs/api/java/util/TreeSet.html

对于一个AVL Tree，有没有所有的O(logn)？上述 TreeSet 方法的复杂性如何？

Answer 1

编辑:应该澄清的是，时间顺序通常是指比较的次数。有些操作没有比较，所以时间顺序可以从子任务的数量中获取

下面的代码在 Java 8 中打印以下内容

O(1) comparisons, however the number of indirections could be O(ln N)
Performing 10,000 first operations -> 0.0 comparisons/operation
Performing 10,000 last operations -> 0.0 comparisons/operation
Performing 10,000 size operations -> 0.0 comparisons/operation
Performing 10,000 isEmpty operations -> 0.0 comparisons/operation
Performing 10,000 comparator operations -> 0.0 comparisons/operation
Performing 10,000 pollFirst operations -> 0.0 comparisons/operation
Performing 10,000 pollLast operations -> 0.0 comparisons/operation
Performing 10,000 headSet operations -> 1.0 comparisons/operation
O(ln N) comparisons
Performing 10,000 add operations -> 12.9 comparisons/operation
Performing 10,000 ceiling operations -> 12.9 comparisons/operation
Performing 10,000 contains operations -> 12.9 comparisons/operation
Performing 10,000 floor operations -> 12.9 comparisons/operation
Performing 10,000 higher operations -> 13.9 comparisons/operation
Performing 10,000 lower operations -> 13.9 comparisons/operation
Performing 10,000 remove operations -> 10.9 comparisons/operation
O(N ln N) comparisons
Performing 10,000 equals operations -> 128853.0 comparisons/operation

代码

public class TreeSetOrderMain {
    public static void main(String[] args) {
        System.out.println("O(1) comparisons, however the number of indirections could be O(ln N)");
        testOrder("first", (s, i) -> s.first());
        testOrder("last", (s, i) -> s.last());
        testOrder("size", (s, i) -> s.size());
        testOrder("isEmpty", (s, i) -> s.isEmpty());
        testOrder("comparator", (s, i) -> s.comparator());
        testOrder("pollFirst", (s, i) -> s.pollFirst());
        testOrder("pollLast", (s, i) -> s.pollLast());
        testOrder("headSet", TreeSet::headSet);

        System.out.println("O(ln N) comparisons");
        testOrder("add", TreeSet::add);
        testOrder("ceiling", TreeSet::ceiling);
        testOrder("contains", TreeSet::contains);
        testOrder("floor", TreeSet::floor);
        testOrder("higher", TreeSet::higher);
        testOrder("lower", TreeSet::lower);
        testOrder("remove", TreeSet::remove);

        System.out.println("O(N ln N) comparisons");
        Set<Long> set = LongStream.range(0, 10_000).mapToObj(i -> i).collect(Collectors.toSet());
        testOrder("equals", (s, i) -> s.equals(set));
    }

    static void testOrder(String desc, BiConsumer<TreeSet<Long>, Long> op) {
        final LongComparator comparator = new LongComparator();
        TreeSet<Long> longs = new TreeSet<>(comparator);
        final int count = 10_000;
        for (long i = 0; i < count; i++)
            longs.add(i);
        comparator.count = 0;
        for (long i = 0; i < count; i++)
            op.accept(longs, i);
        System.out.printf("Performing %,d %s operations -> %.1f comparisons/operation%n",
                count, desc, (double) comparator.count / count);
    }

    static class LongComparator implements Comparator<Long> {
        long count = 0;

        @Override
        public int compare(Long o1, Long o2) {
            count++;
            return Long.compare(o1, o2);
        }
    }
}

---

对单个元素的操作都是 O(ln n) 比较，除了 first 和 last 是 O(1) 比较或 O(ln N) 节点搜索时间。

comparator()、iterator()、clear()、first()、isEMpty()、size()、last()、pollFirst()、pollLast()、headSet() 都是 O(1)

add()、ceiling()、contains()、floor()、higher()、lower()、remove()、subSet()、tailSet() 都是 O(ln N)

clone()、hashCode()、toArray() 和 toString() 的操作复杂度为 O(n)，但没有比较级