Амортизированное время динамического массива
В качестве простого примера, в конкретной реализации динамического массива мы удваиваем размер массива каждый раз, когда он заполняется. Из-за этого может потребоваться перераспределение массива, а в худшем случае для вставки может потребоваться O(n). Однако последовательность из n вставок всегда может быть выполнена за время O (n), потому что остальные вставки выполняются за постоянное время, поэтому n вставок можно выполнить за время O(n). Следовательно, амортизированное время на операцию составляет O(n) / n = O(1). - из вики
Но в другой книге: Каждое удвоение занимает время O (n), но случается так редко, что его амортизированное время все еще равно O (1).
Надеюсь, что кто-то может сказать мне, редкая ситуация выводит Wiki-объяснение? Спасибо
2 ответа
Амортизация в основном означает среднее число операций.
Итак, если у вас есть массив из n, вам нужно вставить n+1 элементов, пока вам не понадобится перераспределение.
Итак, вы сделали n вставок, каждая из которых взяла O(1), и еще одну вставку, которая заняла O (n), так что в итоге вы получили n+1 действий, которые обойдутся вам в 2n операций.
2n / n+1 ~= 1
Вот почему амортизированное время все еще равно O(1)
Да, эти два утверждения говорят об одном и том же, Вики объясняет это более подробно.