1

来自维基百科：

排序列表实施：就像超市的收银台，但重要的人可以在不太重要的人面前“剪掉”。( O(n) 插入时间, O(1) 获取-下一次, O(n*log(n)) 构建)

我认为如果用二分查找算法搜索插入位置，插入时间复杂度应该是O(log(n))。这里我把作业的到达顺序作为一个优先因素。

那么我错了还是维基百科不正确？

更新：根据 TAOCP 对列表的严格定义：

线性列表是 n >=0 节点 X 1 , X[2], ... , X[n] 的序列，其基本结构属性仅涉及项目之间出现在一行中的相对位置。

我假设列表wikipedia 引用不是linked-list，它可能是array。

谢谢。

4

5 回答 5

4

如果它支持链表，则不能进行二进制搜索；找到插入点是O（n），实际上插入是O（1），因为您只是更改相邻节点，总体O（n）。

如果它的数组支持你可以做一个二进制搜索；找到插入点是 O(log(n))，但在数组中插入是 O(n)，因为您可能需要移动数组的所有元素，总体 O(n)

这就是为什么你实际上有树/堆支持，所以所有操作都可以是 O(log(n))

于 2010-02-01T16:53:25.157 回答
3

似乎在您的引用中，维基百科指的是由排序列表支持的优先级队列，而不是堆。将一个项目插入一个排序列表需要 O(n) 时间（假设我们保持它的排序性）。

于 2010-02-01T15:56:36.937 回答
1

二进制搜索确实是O(log n)，但二进制搜索适用于数组 - 它在这个时候有效，因为您可以访问 O(1) 中的任何元素。

但是，在文献中，当您看到术语列表时，您应该考虑链接列表。因此，在列表中，您没有 O(1) 访问时间，而是需要“手动”搜索位置 - 因此插入元素将花费 O(n)。

于 2010-02-01T16:02:10.343 回答
0

排序列表中最坏情况的插入时间是 O(n)。最坏的情况是将最高的项目插入到列表中。为此，您必须遍历所有元素，然后在末尾插入。您不进行二分搜索的原因是，您可以在列表中访问的唯一元素是您当前元素的后继元素，即没有随机访问。

于 2010-02-01T16:02:30.527 回答
0

维基百科是正确的。正如这里的其他人已经说过的那样，列表不是随机访问的，因此您需要在到达 B 之前访问 A 和 B 之间的每个节点。这使得二进制搜索无用，因为遍历列表是 O(n)，所以你最终会比只遍历列表一次做更多的工作。您可以将开始、中间和结束节点缓存在单独的缓冲区中并首先检查它们。但是，这与使用多个列表具有相同的效果。跳过列表数据结构将这一想法更进一步。

因此，请改用随机访问堆，或者可能是跳过列表：http ://en.wikipedia.org/wiki/Skip_list ，具体取决于您的需要。

于 2010-02-01T16:28:59.313 回答