平衡绳的连接复杂度是多少？ [英] What is the concatenation complexity of balanced ropes?

问题描述

我看过不同的论文，这里是我收集的信息：

• SGI实现和 C cords 既不保证长绳的O（1）时间连接，也不保证较短的时间连接。


• 不同的来源相互矛盾。 维基百科声明O（1）连接。 此页表示，仅当一个操作数为小和O（log N）否则。

那么，连接的时间复杂度是多少？当执行重新平衡以确保这种连接复杂性同时保持树平衡？在讨论这种复杂性时，是否采用了一些具体的使用模式？

解决方案

维基百科的文章不清楚，文章绳索：替代字符串

另一方面，最近的这篇文章（由GerthStøltingBrodal，Christos Makris和Kostas Tsichlas） ：纯功能最差病例恒定时间可连接分类列表。他们也有O（logn）搜索，所以确实你可以标记它平衡，我还没有阅读细节，只是结果。

绳是一个在实践中（相对）常见的术语，但不是在研究中。相反，我搜索了 catenable queues （或列表），特别是人们作为Tarjan，Okasaki，Kaplan和其他人做的研究，我认为这是你真正的答案。 p>

I've looked at different papers and here is the information that I've gathered:

• SGI implementation and C cords neither guarantee O(1) time concatenation for long ropes nor ~log N depth for shorter ones.
• Different sources contradict each other. Wikipedia claims O(1) concatenation. This page says that concatenation is O(1) only when one operand is small and O(log N) otherwise.

So, what is the time complexity of concatenation? When exactly rebalancing is performed to ensure this concatenation complexity while maintaining tree balance? Are some specific usage patterns assumed when talking about this complexity?

解决方案

The wikipedia article is unclear, the paper "Ropes: an Alternative to Strings" that it cites nowhere, claims such a complexity result.

On the other hand, this recent paper (by Gerth Stølting Brodal, Christos Makris and Kostas Tsichlas) does: "Purely Functional Worst Case Constant Time Catenable Sorted Lists". They also have O(logn) search, so indeed you can tag it "balanced", I haven't read the details though, just the results.

"Rope" is a term that is (relatively) common in practice, but not in research. Instead, I searched for catenable queues (or lists), especially research done by people as Tarjan, Okasaki, Kaplan and others, I think that's where your real answer is.

这篇关于平衡绳的连接复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！