获取数组的最后一个索引的时间复杂度是多少？

Question

array = ["A", "B", "C", "D"]

对于给定的数组，需要O(1)指向第一个索引0。所以如果我输入array[0]，它需要O(1)来指向"A"。但是如果我写array[-1]，它指向最后一个索引3。它是遍历整个数组以获得最后一个索引还是知道数组在默认情况下以索引3结束？ 换句话说，array[-1]是如何在python中实现的？在

Answer 1

访问任何数组元素的时间都是固定的，因为它是内存已知的位置（即指针）

数组不需要遍历前面的元素就可以访问第n个元素（也就是说，它不像一个链表），所有元素的位置都是事先知道的，可以直接访问。在

更新感谢评论。在

array[-x]是array[len(lst) - x]的语法糖。所以它仍然是一个简单的常量访问指针，不需要时间。在

You can see this answer for a bit more info. While it is about C, the concepts should be the same.

Answer 2

原生Python列表是指针数组，访问任何元素都是O（1）。在

请注意，这是一个特定于标准Python实现（称为CPython）的实现细节。其他语言实现可能以不同的方式实现列表。在