Амортизированное время динамического массива

Question

Как простой пример, в конкретной реализации динамического массива мы каждый раз увеличиваем размер массива. Из-за этого может потребоваться перераспределение массива, и в худшем случае для вставки может потребоваться O (n). Тем не менее, последовательность n вставок всегда может выполняться в O (n) времени, так как остальные вставки выполняются в постоянное время, поэтому n вложений может быть завершено в O (n) времени. Таким образом, амортизированное время на операцию O (n)/n = O (1). - from Wiki

Но в другой книге: каждое удвоение принимает время O (n), но бывает так редко, что его амортизированное время все еще O (1).

Надеюсь, что кто-нибудь может сказать мне, делает ли редкая ситуация вывод о вики-объяснении? Спасибо

Answer 1

Да, эти два утверждения говорят одно и то же, Wiki просто объясняет это более подробно.

Answer 2

Амортизация в основном означает среднее количество операций.

Итак, если у вас есть массив n, вам нужно вставить n + 1 items, пока вам не понадобится перераспределение.

Итак, вы сделали п вставки, которые каждый из них взял O (1), а другая вставка, которая приняла O (N), так что в общей сложности у вас есть п + 1 действия, который стоит вам 2n операций.

2n/n+1 ~= 1 

Вот почему Амортизационные время еще O (1)