7

我查看了不同的论文，以下是我收集的信息：

  • SGI 实现和C 绳既不能保证长绳索的 O(1) 时间连接，也不能保证较短绳索的 ~log N 深度。
  • 不同的来源相互矛盾。维基百科声称 O(1) 级联。该页面说，仅当一个操作数较小时，连接才为 O(1)，否则为 O(log N)。

那么，串联的时间复杂度是多少？何时执行重新平衡以确保这种连接复杂性同时保持树平衡？在谈论这种复杂性时，是否假设了一些特定的使用模式？

4

1 回答 1

3

维基百科的文章不清楚，它在任何地方都没有引用的论文“绳索：字符串的替代品”声称如此复杂的结果。

另一方面，这篇最近的论文（由 Gerth Stølting Brodal、Christos Makris 和 Kostas Tsichlas 撰写）确实：“Purely Functional Worst Case Constant Time Cateable Sorted Lists”。他们也有 O(logn) 搜索，所以你确实可以将它标记为“平衡”，但我还没有阅读详细信息，只是结果。

“绳索”是一个在实践中（相对）常见的术语，但在研究中并不常见。相反，我搜索catenable queues（或列出），尤其是 Tarjan、Okasaki、Kaplan 等人所做的研究，我认为这才是你真正的答案所在。

于 2010-10-13T16:20:33.520 回答