Java中TreeSet部分视图的size（）复杂度是多少 [英] What is complexity of size() for TreeSet portion view in Java

问题描述

我想知道TreeSet的部分视图的 size（）的时间复杂度是什么。

I'm wondering what is the time complexity of size() for portion view of TreeSet.

假设我正在添加随机数来设置（我不关心重复）：

Let say I'm adding random numbers to set (and I do not care about duplicities):

    final TreeSet<Integer> tree = new TreeSet<Integer>();
    final Random r = new Random();
    final int N = 1000;
    for ( int i = 0; i < N; i++ ) {
        tree.add( r.nextInt() );
    }

现在我正在讨论的复杂性size（）调用：

    final int M = 100;
    for ( int i = 0; i < M; i++ ) {
        final int f = r.nextInt();
        final int t = r.nextInt();
        System.out.println( tree.headSet( t ).size() );
        System.out.println( tree.tailSet( f ).size() );
        if ( f > t ) {
            System.out.println( tree.subSet( t, f ).size() );
        } else {
            System.out.println( tree.subSet( f, t ).size() );
        }
    }

树的AFAIK复杂性。 headSet（t）， tree.tailSet（f）和 tree.subSet（f，t）是O（lg N）， set.size（）是O（1），但是 size（）上面的方法？我有一种不好的感觉，它是O（K），其中K是所选子集的大小。

AFAIK complexity of tree.headSet( t ), tree.tailSet( f ) and tree.subSet( f, t ) are O(lg N), set.size() is O(1), but what about size() methods above? I have such a bad feeling that it's O(K) where K is size of selected subset.

也许如果有一些解决方法来查找设置中某个元素的索引就足够了，因为如果我能得到 ti = indexOf（f），那就说O（lg N）比我所需要的还要多。

Maybe if there is some workaround to find index of some element in set it would be enough, because if I can get ti = indexOf(f), in let say O(lg N) than it is exactly what I need.

推荐答案

看起来 size（）的复杂性是 O（N ），因为它可以调用 TreeMap.NavigableSubMap.EntrySetView.size（）这样实现（Oracle JDK 1.7.0_13）：

Looks like complexity of size () is O(N), because it may call TreeMap.NavigableSubMap.EntrySetView.size () which is implemented like this (Oracle JDK 1.7.0_13):

public int size() {
    if (fromStart && toEnd)
        return m.size();
    if (size == -1 || sizeModCount != m.modCount) {
        sizeModCount = m.modCount;
        size = 0;
        Iterator i = iterator();
        while (i.hasNext()) {
            size++;
            i.next();
        }
    }
    return size;
}

这篇关于Java中TreeSet部分视图的size（）复杂度是多少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！