我想知道为什么动态数组末尾追加元素的时间复杂度是0(1)
这里我已经考虑到动态数组还没有满。
例如在Python中，想象一个大小为6的列表并且只填充了3个元素：
a = [ 1, 2, 3 , _ , _ , _ ]
a.append(4)
现在当我向第三个索引添加一个元素时，为什么时间复杂度是 0(1) 而不是 0(n) ？是否有一个指针指向数组的最后一个元素？还是还有其他机制？
因为要将元素添加到第三个索引，我需要遍历到第三个索引并添加元素，对吧？或者追加的工作方式不同吗？
是的，基本上动态数组在内部与普通数组一样工作。当您不断向动态数组添加元素时，它的大小会在内部不断增加。由于动态数组在内部使用普通数组，因此它使用索引来添加和检索数组中的元素。因此，当您向动态数组添加元素时，动态数组的时间复杂度也为 O(1)。
准确地说，在动态数组末尾追加项的时间复杂度是摊销 O(1)。这意味着在大多数情况下，当有足够的内存分配给数组增长时，它是 0(1)。如果没有为动态数组分配足够的内存，则可能需要将所有元素复制到另一个位置 - 即 O(n)，但这被认为是一种罕见的情况。