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

Question

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

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

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

Answer 1

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

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

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

2n / n+1  ~= 1 

Вот почему амортизированное время по-прежнему O (1)

Answer 2

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