1

我对从跳过列表中插入或删除元素所需的时间有点困惑。

假设有一个高度为 H 的跳过列表，每个级别包含 n/2^i 个条目。
n = 键值对总数
i = 跳过列表的级别 i<= H

现在，根据理论，插入操作将执行以下操作
1. 找到一个键 <= 正在插入的键。
2. 插入此键
3. 在基础级别以上的级别中随机创建此条目。

让我们假设 Skip 列表基于链表。
第 1 步：应该取 O(n)。
第 2 步：应该是 O(1)。
第 3 步：应该是 O(log n) 时间。我仍然对这个逻辑感到困惑，它将成为下面问题的一部分

问题

  1. 基于上述事实，插入时间不应该是 O(n) + O(1) + O(log n) 吗？忽略低阶项，它应该是 O(n) + O(log n)？

  2. 第 3 步再次应该花费 O(n) 时间来搜索要插入的密钥 <= 密钥，然后需要 o(1) 时间来插入。导致非常复杂的插入运行时间？

书上说插入跳过列表需要 O(log n) 时间。我一定错过了一些重要的信息，请你帮我很好地理解这个概念。

4

2 回答 2

1

由于跳过列表用于存储已排序的数据，因此在查找插入新元素的位置时，您可以执行比线性搜索更智能的操作。

基本上，您可以使用更高级别的指针执行类似于二进制搜索的操作。例如，通过检查log n - 1第 th 级的链接，您可以将新项目与列表中间的项目进行比较，从而确定它应该插入到列表的前半部分还是后半部分。然后您继续这样，每次查看较低级别的链接以获得更好的精度。这将算法中步骤 1 的复杂度降低到O(log n).

于 2012-09-01T21:17:16.677 回答
1

跳过列表的全部意义在于不必遍历整个列表来查找项目。您首先在上面的列表中搜索，然后向下一层，依此类推，直到到达基本列表。

假设顶部列表包含 2 个项目，第一个项目和一个在中间的某个位置。当您搜索您的项目时，该列表已被减半。每个级别都会将列表大约减半。这就是插入 O(log n) 的原因。

于 2012-09-01T21:18:21.230 回答