2

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

4

1 回答 1

1

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

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

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

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

于 2013-10-31T07:19:45.447 回答