data-structures - 将新项目添加到基于数组的列表后面的时间复杂度

Question

如果有人问我：“在基于数组的列表后面添加新项目的运行时间复杂度是多少？” 我需要怎么回答？它可以被视为是，O(1)因为它是随机访问。但是如果resize()在插入之前调用该方法（该resize()方法用于在数组已满时将其大小增加一倍）怎么办？在这种情况下将是线性时间。因此，哪一个是正确的？O(1)还是O(n)？

Answer 1

摊销，它是 O(1)，尽管它取决于增加列表大小的策略。

如果我们只是在数组已满时将其大小增加一，则为 O(n)，因为当我们执行许多插入时，我们必须为每个插入复制整个列表。

如果每次数组满时我们将其大小加倍，我们将相对较少地进行复制。摊销或平均，这变为 O(1)。

这种数据结构通常称为动态数组。