这是平衡的绳索的级联复杂？ [英] What is the concatenation complexity of balanced ropes?

问题描述

我看着不同的文件，这里是我所收集到的信息：

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

• SGI实现和的Ç线的既不保证O（1）时间串联长的绳索，也没有与NBSP ;〜登录＆NBSP; N深度较短的
• 在不同来源的相互矛盾。 维基百科声称O（1）连接。 此页面说，串联是O（1）只有当一个操作数小O（日志N）的除外。

• 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.

在另一方面，这个最近的一篇文章（格斯（Gerth）由StøltingBrodal，克里斯托Makris和科斯塔斯·Tsichlas）确实：纯功能最差情况下的恒定时间Catenable排序的列表。他们也有O（LOGN）搜索，所以实际上你可以将其标记为平衡，我没有看到细节，虽然，只是结果。

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.

绳是一个术语，是（相对）共同在实践中，但不是在研究。相反，我搜索 catenable队列（或清单），特别是研究由人来完成的的Tarjan，Okasaki，卡普兰和其他人，我想这是你真正的答案是。

"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屋！