TreeSet 中有序操作的时间复杂度是多少?

发布于 10-20 11:49 字数 322 浏览 5 评论 0原文

中以下操作的时间复杂度是多少java.util.TreeSet

  • first()
  • last()
  • lower()
  • higher()

我假设这些是常数时间,但是API 不提供任何保证。

What is the time complexity of the following operations in java.util.TreeSet?

  • first()
  • last()
  • lower()
  • higher()

I would assume that these are constant time but the API makes no guarantees.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(5

多情出卖2024-10-27 11:49:04

实际上,我原以为这些操作对于一般实现来说都是O(logN)

  • 要使 first()last() 的时间复杂度为 O(1),TreeSet 实现需要维护一个指向最左边的指针和树中最右边的叶节点。维护这些会为每次插入增加恒定成本,并且至少为每次删除增加恒定成本。实际上,该实现可能会动态找到最左/最右节点...这是一个 O(logN) 操作。

  • lower()higher() 方法必须执行与 get 相同的工作,因此 O(logN )

当然,您可以自己检查源代码,看看实际发生了什么。 (正如其他人所做的那样:见下文。)

Actually, I'd have thought that those operations are all going to be O(logN) for a general implementation.

  • For first() and last() to be O(1) the TreeSet implementation would need to maintain a pointer to the leftmost and rightmost leaf nodes in the tree respectively. Maintaining these adds a constant cost to every insertion and at least a constant cost to every deletion. In reality, the implementation will probably find the left / rightmost nodes on the fly ... which is an O(logN) operation.

  • The lower() and higher() methods have to do the same work as get and are therefore O(logN).

Of course, you can check the source-code yourself to see what actually happens. (As other people have done: see below.)

梦言归人2024-10-27 11:49:04

根据 TreeSet 默认使用的 TreeMap 的实现(sun jdk 1.6.0_23),看起来first()和last()都是O(log n)而不是O(1):

 /**
 * Returns the first Entry in the TreeMap (according to the TreeMap's
 * key-sort function).  Returns null if the TreeMap is empty.
 */
final Entry<K,V> getFirstEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.left != null)
            p = p.left;
    return p;
}

/**
 * Returns the last Entry in the TreeMap (according to the TreeMap's
 * key-sort function).  Returns null if the TreeMap is empty.
 */
final Entry<K,V> getLastEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;
}

Looks like both first() and last() will be O(log n) and not O(1)based on Implentation(sun jdk 1.6.0_23) of TreeMap which is used by TreeSet by default:

 /**
 * Returns the first Entry in the TreeMap (according to the TreeMap's
 * key-sort function).  Returns null if the TreeMap is empty.
 */
final Entry<K,V> getFirstEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.left != null)
            p = p.left;
    return p;
}

/**
 * Returns the last Entry in the TreeMap (according to the TreeMap's
 * key-sort function).  Returns null if the TreeMap is empty.
 */
final Entry<K,V> getLastEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;
}
清引2024-10-27 11:49:04

其实我查了一下源码
http://developer.classpath.org/doc/java/util/ TreeSet-source.html,first()调用maps.firstKey()
然后在
http://developer.classpath.org/doc/java/util/TreeMap -source.html

393: public K firstKey()
394: (
395: if (root == nil)
396: throw new NoSuchElementException();
397: return firstNode().key;
398: )

并在firstNode()中,它执行while循环一直到左边

952: final Node<K, V> firstNode()
953: (
954: // Exploit fact that nil.left == nil.
955: Node node = root;
956: while (node.left != nil)
957: node = node.left;
958: return node;
959: )

I actually looked up the source code,
in http://developer.classpath.org/doc/java/util/TreeSet-source.html, first() calls maps.firstKey()
then in
http://developer.classpath.org/doc/java/util/TreeMap-source.html

393: public K firstKey()
394: (
395: if (root == nil)
396: throw new NoSuchElementException();
397: return firstNode().key;
398: )

and in firstNode(), it does the while loop to go all the way to the left

952: final Node<K, V> firstNode()
953: (
954: // Exploit fact that nil.left == nil.
955: Node node = root;
956: while (node.left != nil)
957: node = node.left;
958: return node;
959: )

这将取决于实施情况。我对JAVA不是很熟悉,但似乎所有这些操作都是遍历操作(获取最低元素,获取最高元素,获取下一个更高或下一个更低)。

如果树被实现为自平衡二叉搜索树,就像AVL 树,或任何其他类型的平衡树结构,您将看到平均情况每个操作的最坏情况为 O(log n) 时间,最好情况为 O(1)。

It's going to depend on the implementation. I'm not incredibly familiar with JAVA, but it seems that all of those operations are traversal operations (get lowest element, get highest element, get next higher or next lower).

If the Tree is implemented as a Self-Balancing Binary Search Tree like an AVL Tree, or any other sort of a balanced-tree structure, you're going to be looking at Average-Case and Worst-Case O(log n) time for each of the operations, and a best case of O(1).

不…忘初心2024-10-27 11:49:04

API 不提供任何保证,因为这些保证基于 trie 的标准模型。最好的情况是 O(1),平均情况是 O(log n),最坏情况是 O(n)。

从文档中:

此实现为基本操作(添加、删除和包含)提供有保证的 log(n) 时间成本。

这些不是您要求的功能,但请考虑一下 Java 将如何遍历 TreeSet。

The API makes no guarantees because these are based on the standard model of a trie. The best case is in O(1), with the average case being O(log n) and worst case O(n).

From the documentation:

This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

These aren't the functions you asked for, but think about how Java will traverse the TreeSet.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文