工件表和绳索的java时间复杂性
我正在阅读各种文本编辑器背后的数据结构，有几个问题
如果我理解正确，在工件表上搜索/遍历是O（n），因为您需要逐个遍历链表，而Rope只需要O（logn）时间，因为它是一个平衡的二叉树
那么为什么在{a1}和{a2}中，它声称“插入几乎成为恒定时间操作”和“在大多数数据处理例程中，需要顺序访问rope的字符，在这种情况下，rope迭代器可以提供摊销O（1）访问速度”。我是不是遗漏了什么？它们不应该都是O（logn）吗，因为它们需要先找到叶子的位置
欢迎所有反馈/回答！ 干杯
# 1 楼答案
你问了两个问题：
问题1。“插入”如何成为几乎恒定的时间操作
A1。因为有些人认为O（logn）是“几乎恒定的时间”。你可能不同意那些人
问题2。“对rope字符的顺序访问是必需的，在这种情况下，rope迭代器可以提供O（1）访问速度”
A2。顺序访问与搜索不同。您假设“工件表上的搜索/遍历是O（n），因为您需要逐个遍历链表，而Rope只需要O（logn）时间”，但该语句将具有不同访问成本的两个操作（搜索和遍历）合并在一起
遍历数据结构通常至少需要Ω（n）的时间，因为您必须遍历每个元素。另一方面，对于某些数据结构，搜索可以是O（1）
现在，我们已经理清了这个问题，让我们来检查一下您所问的陈述：“顺序存取…摊销O（1）”是什么意思？这意味着您可以搜索给定位置，然后在O（1）摊销时间内依次遍历。平衡搜索树上的这些边界通常是O（logn+k），其中k是遍历的项目数。如果k为Ω（对数n），则为O（k），即每个项目的O（1）