2

我正在优化排序的 LinkedList 的实现。

要插入一个元素，我遍历列表并比较每个元素，直到我有正确的索引，然后中断循环并插入。

我想知道是否有任何其他方式可以在遍历列表的同时插入元素以将插入从 O(n + (n capped at size()/2)) 减少到 O(n) .

ListIterator几乎是我所追求的，因为它的 add() 方法，但不幸的是，在列表中存在等于插入的元素的情况下，插入必须放在列表中它们之后。要实现这个 ListIterator 需要一个它没有的 peek()。

编辑：我有我的答案，但无论如何都会添加这个，因为很多人还没有正确理解： 我正在寻找一个插入点和插入，它的总和高于 O(n)

4

3 回答 3

2

您可以考虑使用多个链表以不同粒度实现的跳过列表。例如，第 0 级的链表包含所有项目，第 1 级平均仅链接到每个第 2 个项目，第 2 级平均仅链接到每个第 4 个项目，等等......搜索从顶层开始，逐渐下降到较低级别，直到它找到一个完全匹配的。这个逻辑类似于二分查找。因此搜索和插入是一个 O(log n ) 操作。

Java 类库中的一个具体示例是ConcurrentSkipListSet（尽管在这里可能无法直接用于您）。

于 2012-04-02T09:23:12.167 回答
1

我赞成 Péter Török 的建议，但我仍然想为迭代器方法添加一些内容：

请注意，它ListIterator提供了previous()一种向后迭代列表的方法。因此，首先迭代，直到找到第一个更大的元素，然后转到前一个元素并调用add(...). 如果你到达终点，即所有元素都更小，那么就直接调用add(...)而不返回。

于 2012-04-02T09:33:02.963 回答
0

我有我的答案，但无论如何都会添加这个，因为很多人没有正确理解：我正在寻找一个插入点和插入，它的组合高于O(n).

您需要维护一组（可能）非唯一元素，这些元素可以按照排序函数给出的顺序进行迭代。这可以通过多种方式实现。（在下文中，我使用“总插入成本”来表示将多个 ( N) 元素插入到最初为空的数据结构中的成本。）

  • 单链表或双链表提供O(N^2)总插入成本（无论您是否将查找位置和执行插入的步骤结合起来！）和O(N)迭代成本。

  • TreeSet 提供O(NlogN)总插入成本和O(N)迭代成本。但是有没有重复的限制。

  • 基于树的多重集（例如TreeMultiset）具有与 TreeSet 相同的复杂性，但允许重复。

  • 跳过列表数据结构也具有与前两种相同的复杂性。

显然，复杂性度量表明，当 N 变大时，使用链表的数据结构性能最差。对于这组特殊的需求，一个良好实现的基于树的多重集可能是最好的，假设只有一个线程访问该集合。如果该集合被许多线程大量使用（并且它是一个集合），那么 aConcurrentSkipListSet可能更好。

您似乎也对“大 O”措施如何组合存在误解。如果我有一个算法的一个步骤是O(N)，第二个步骤也是O(N)，那么这两个步骤结合起来仍然O(N)......不是“超过O(N)”。您可以从“大 O”的定义中得出这一点。（我不会让你厌烦细节，但数学很简单。）

于 2012-04-02T11:12:57.037 回答