我正在实现优先级队列，并希望遍历列表以在正确的位置插入。在文档中指出C#List<T>.Item属性为O(1):
List<T>.Item Property
例如
int retrivedValue = myIntList[5];
由于add也为O(1)，这怎么可能？就像吃了 cookies ，仍然有它。我脑海中的普通列表具有O(n)用于访问元素。
最佳答案
List<T> 是表示形式的列表，如文档所述，它表示可以通过索引访问的对象的类型化列表。它的元素可以通过索引直接访问，并且不需要逐个元素遍历，因此，访问元素的时间复杂度为O(1)。它在内部实现为动态数组，这种类型在填满时会使其大小加倍(感谢注释!)。
您可能将它与 LinkedList<T> 混淆了，后者被实现为链接列表...
关于c# - List <T> .Item属性如何成为O(1)？错别字？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22828081/