List <T> .Item属性如何为O(1)？错字？
Joh*_*tby 27 c# list list-template
我正在实现一个优先级队列,并希望迭代列表以插入正确的位置.在文档中,它声明C#List<T>.Item属性是O(1):
List<T>.Item属性
例如
int retrivedValue = myIntList[5];
这是怎么可能的,因为add也是O(1)？就像吃饼干一样,仍然拥有它.我头脑中的普通列表有O(n)用于访问元素.
Art*_*amz 23
List<T>是一个表示的列表,正如文档所说,它表示可以通过索引访问的对象的类型列表.它的元素可以通过索引直接访问,并且不需要逐个元素遍历,因为访问元素的时间复杂度是O(1).它在内部实现为一个动态数组,当它填满时它的大小加倍(感谢评论!).
您可能会混淆它LinkedList<T>,它被实现为链接列表...
- 你似乎在说访问元素是O(n)而不是O(1)这是正确的还是这是一个错字？你对我的论证暗示O(1)这就是为什么我认为这可能是一个错字. (2认同)
Gab*_*abe 22
它List<T>由一个数组支持.
该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).
- -1.Big-O表示法谈论渐近行为.所以我不得不问; 当你说'但是第5个必须复制现有的4个元素并添加第5个,使其成为O(5)'什么是操作O(5)？正确的措辞是; '对于两次操作的每一次操作,我们需要进行一次操作,其运行时间与列表的当前长度成比例.O(1 + 2 + 4 + 8 + 16 + ... + x ^ 2)= O(2*x ^ 2)= O(n ^ 2),因此只有最终的这种操作才有意思.这是O(n)运算,O(n + 1 + 1 + 1 + ...(n 1))= O(2n)= O(n).所以我们有O(n)时间进行n次插入. (4认同)
- 我想对此进行一点扩展.你应该强调*大多数*操作(添加)是O(1),而不是一些,*某些*太弱.您的最终结论应该是添加单个元素平均为O(2)= O(1).(你忘了加上你添加N个元素的事实) (2认同)
- 设计`List <T>`是可能的,这样每个追加或索引操作都会花费恒定的时间,如果一个列表的大小加倍,则保留前一个列表,并且每次将一个项目添加到新列表,项目从旧项目移动.一旦需要重新扩展列表,可以放弃旧列表.这种方法最终会和`List <T>`做同样的工作; "List <T>"的优点源于这样一个事实:物品可以比零碎地更快地复制,查找需要检查一个数组而不是两个数组. (2认同)
尽管基于元素索引吸引力列表搜索的复杂性,我不知道您的需求可能被SkipList得到更好的服务,如描述使用C#2.0的数据结构全面检查提到这里,作为排序优先级是不是唯一的.
为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).
Skiplists具有O(logn)搜索复杂度; 允许PriorityQueue O(logn)入队和O(1)出队
想法是SkipList是一个链接列表,其中包含随机插入的"快进"指针,以克服链接列表的O(n)搜索复杂性.每个节点都有一个高度K和K的下一个指针.没有详细说明,高度是分布式的,next()函数选择适当的指针,以便进行搜索O(logn).但是,要从队列中删除的节点始终位于链表的一端.
在线行为
内存是有限的,实际上优先级队列不会永远增长.有人可能会争辩说队列增长到一定的大小然后再也没有被重新分配.但那么,它会缩小吗？如果列表变得碎片化,收缩操作听起来比成长操作更昂贵.如果支持收缩,则每次List增长过小时都会支付成本,然后在List增长过大时支付增长成本.如果不支持,则与最大队列大小关联的内存将保持分配状态.这是一个优先级队列,事实上它确实可能是一个队列可以随着工作进入它而增长,然后收缩(逻辑上)为0.如果消费者方面滞后,可能会有罕见的情况会变得非常大.
List内部使用数组,因此索引是直接操作.此外,最后添加速度很快(除非需要realoc).插入和删除是O(n),因为数组的所有元素都需要移动.在实践中,这也不是那么糟糕,因为移动是作为阵列右侧部分的单个块移动实现的.