我正在阅读有关各种文本编辑器背后的数据结构，并且有几个问题。件表和绳的时间复杂度
如果我正确地理解了这一点，Piece Table上的搜索/遍历是O（n），因为您需要逐个浏览链接列表，而Rope仅需要O（logn）时间，因为它的结构为平衡二叉树。
那为什么在this stackoverflow answer和this IBM article，它声称“插入成为近固定的时间操作”和“在大多数数据处理程序，一根绳子的字符顺序访问是我们需要的，在这种情况下，绳索迭代器可以提供分期付款的O（1）访问速度“。我在这里错过了什么吗？他们不应该都是O（logn），因为他们需要先找到叶子的位置？
欢迎所有反馈/答复！ 干杯！
您问了两个问题：
Q1。如何“插入几乎不变的时间操作”？
A1。因为有些人认为O（log n）是“几乎恒定的时间”。你可能会不同意这些人。 Q2302。如何“顺序访问一个绳索的角色是需要的，在这种情况下，一个绳索迭代器可以提供分期的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）。
也许这意味着你已经拥有了叶子和叶子中的位置。 – Dialecticus
@Dialecticus也许，但似乎在这种情况下表明明显。 – zokland
你的问题至少有七个问题。一直以来我的观察是，只有一个重点问题的帖子才能得到更多答案。 – jbapple