我正在实现一个优先级队列，并希望遍历列表以在正确的位置插入。在文档中，它指出 C# List<T>.ItemProperty is O(1):
List<T>.ItemProperty
例如
int retrivedValue = myIntList[5];
这怎么可能，因为 add 也是 O(1)？这就像吃了饼干并且仍然拥有它。我脑海中的普通列表有 O(n) 用于访问元素。
问问题
7328 次
7 回答
23
List<T>是一个表示形式的列表，正如文档所说，它表示可以通过 index 访问的对象的类型列表。它的元素可以通过索引直接访问，不需要逐个元素遍历，所以访问一个元素的时间复杂度是O(1)。它在内部实现为动态数组，当它填满时，它的大小会加倍（感谢评论！）。
你可能会混淆它LinkedList<T>，它是作为链表实现的......
于 2014-04-03T04:51:40.567 回答
22
由List<T>数组支持。
该Add操作在所有 add 中摊销为 O(1) ，这意味着大多数操作是 O(1)，但有些是 O(N)。每当后备数组填满时，它就会被复制到一个两倍大小的新数组中。
作为其工作原理的示例，假设支持数组以 4 个元素开始。前 4 个添加是 O(1)，但第 5 个必须复制现有的 4 个元素并添加第 5 个，使其成为 O(5)。添加元素 6、7 和 8 是 O(1)，而添加元素 9 将是 O(9)。那么元素 10-16 也将是 O(1)。
当您向数组添加 16 个元素时，您已经完成了 O(28) 次操作，使得添加 N 个元素几乎需要 O(2N) 次操作。因此，添加单个元素平均为 O(2) = O(1)。
于 2014-04-03T05:06:28.510 回答
9
于 2014-04-05T21:41:39.180 回答
8
只有O(n)当您必须遍历列表以检索项目时，您才有。
对于此示例，您通过索引访问内部数组，因此不必迭代。
于 2014-04-03T04:49:09.230 回答
6
尽管基于元素索引的列表搜索复杂性很有吸引力，但我想知道您的需求是否可以通过使用 C# 2.0 对数据结构进行广泛检查中所述的SkipList更好地满足，因为排序优先级不是唯一的。
为 n 次插入（n 无界）动态扩展数组实际上是 O(n)
如果列表的数组支持每次都加倍大小并且允许 n 无限制地增长，那么重新分配数组的次数将为 O(logn) 并且每个点的大小为 2^k；k = 1,2,3...
List<T>.Item versus List<T>.Contains
如果索引已知，则访问 List 中的元素是 O(1)，但要根据优先级保持正确的顺序，您需要使用一些外部排序机制或使用.Contains，但第二种方法不是 O (1)。
Skiplist 的搜索复杂度为 O(logn)；允许 PriorityQueue O(logn) 入队和 O(1) 出队
这个想法是 SkipList 是一个带有随机插入的“快进”指针的链表，以克服链表的 O(n) 搜索复杂性。每个节点都有一个高度 K 和 K 个下一个指针。无需详细说明，高度是分布的，并且 next() 函数以这样的方式选择适当的指针以进行搜索 O(logn)。但是，要从队列中删除的节点总是位于链表的一端。
在线行为
内存是有限的，实际上优先级队列不会永远增长。有人可能会争辩说队列增长到一定大小，然后永远不会被重新分配。但是，它会缩小吗？如果列表变得支离破碎，收缩操作听起来比增长操作成本更高。如果支持shrink，则每次List增长过小时都会支付费用，然后当List增长过大时会支付增长费用。如果不支持，则与最大队列大小关联的内存将保持分配状态。这是一个优先级队列，事实上，队列可能会随着工作的加入而增长，然后（逻辑上）缩小到 0。如果消费者方面滞后，它可能会变得非常大，这种情况很少见。
于 2014-04-03T17:27:59.357 回答
5
List 内部使用数组，因此索引是直接操作。此外，最后添加很快（除非需要重新分配）。但是，插入和删除是 O(n)，因为数组的所有元素都需要移动。实际上，这也不是那么糟糕，因为移动是作为数组右侧部分的单个块移动来实现的。
于 2014-04-03T05:01:40.160 回答