java - 棋子表和绳子的时间复杂度

Question

我正在阅读各种文本编辑器背后的数据结构，并有几个问题。

如果我理解正确，在 Piece Table 上搜索/遍历是 O(n)，因为您需要一个接一个地遍历链表，而 Rope 只需要 O(logn) 时间，因为它是一个平衡的二进制结构树。

那怎么进来this stackoverflow answer和 this IBM article ，它声称“插入几乎成为恒定时间操作”并且“在大多数数据处理中在例程中，顺序访问绳索的字符是必需的，在这种情况下，绳索迭代器可以提供摊销的 O(1) 访问速度”。我在这里错过了什么吗？他们不应该都是 O(logn) 因为他们需要先找到叶子的位置吗？

欢迎所有反馈/答案!干杯!

Answer 1

你问了两个问题:

Q1。如何“插入成为几乎恒定时间的操作”？

A1。因为有些人认为 O(log n) 是“几乎恒定的时间”。你可能不同意那些人。

Q2。如何“顺序访问绳索的字符是所需要的，在这种情况下绳索迭代器可以提供分摊的 O(1) 访问速度”？

A2。顺序访问不同于搜索。您假设“在 Piece Table 上搜索/遍历是 O(n)，因为您需要一个接一个地遍历链表，而 Rope 只需要 O(logn) 时间”，但是该语句将两个操作(搜索和遍历)混为一谈具有不同的访问成本。

遍历一个数据结构至少需要 Ω(n) 的时间，因为你必须遍历每个元素。另一方面，对于某些数据结构，搜索 可以是 O(1)。

现在我们已经理清了这一点，让我们检查一下您提出的问题:“顺序访问 ... 分摊 O(1)”是什么意思？这意味着您可以搜索给定位置，然后在 O(1) 摊销时间内按顺序遍历。平衡搜索树上的这些边界通常为 O(log n + k)，其中 k 是遍历的项目数。如果 k 为 Ω(log n)，则为 O(k)，即每个项目的 O(1)。