1

我需要在 Java 中为平衡树实现迭代器函数，例如 AVL 树，其摊销复杂度为 O(1+log(N/M))，但不确定这意味着什么？任何链接或解释都会非常有帮助..谢谢

4

1 回答 1

1

这意味着对于迭代器的next()方法的每次连续调用，该方法调用的复杂性都会降低。对于具有 N 个节点的树，第一次调用的复杂度应该是 O(log(N))，接下来的调用应该有 O(log(N/2))，等等。要真正理解复杂性，你应该有一些背景知识数学和计算机科学。在这里阅读一个简短而模棱两可的解释。为了更深入地理解这个主题，你应该从 Corman 的算法简介开始

于 2013-03-24T21:37:17.250 回答