Как показано в документации для TimeComplexity, реализован тип Python list, используя массив.
Итак, если массив используется, и мы делаем несколько добавлений, в конечном итоге вам придется перераспределить пространство и скопировать всю информацию в новое пространство.
В конце концов, как это может быть O (1) наихудший случай?
Если вы посмотрите на сноску в связанном документе, вы увидите, что они содержат оговорку:
Эти операции основаны на "Амортизированной" части "Амортизированный худший" Случай ". Индивидуальные действия могут занимать удивительно долго, в зависимости от история контейнера.
Используя амортизированный анализ, даже если нам приходится иногда выполнять дорогостоящие операции, мы можем получить более низкую оценку "средней" стоимости операций когда вы рассматриваете их как последовательность, а не индивидуально.
Таким образом, любая отдельная операция может быть очень дорогой - O (n) или O (n ^ 2) или что-то еще большее - но поскольку мы знаем, что эти операции редки, мы гарантируем, что последовательность операций O (n) может выполняться в O (n) времени.
Он амортизировал O (1), а не O (1).
Предположим, что зарезервированный размер списка составляет 8 элементов, и он удваивается по размеру, когда пространство заканчивается. Вы хотите нажать 50 элементов.
Первые 8 элементов вставляют O (1). Nineth запускает перераспределение и 8 копий, за которым следует push (1). Следующие 7 нажимают O (1). Семнадцатые триггеры перераспределяют и 16 копий, за которым следует кнопка O (1). Следующие 15 нажмите O (1). Тридцать третье триггеры перераспределяют и 32 копии, за которым следует кнопка O (1). Следующие 17 нажмите O (1).
Таким образом, все толки имеют O (1) сложность, у нас было 56 копий при O (1) и 3 перераспределения в O (n) с n = 8, 16 и 32. Заметим, что это геометрическая и асимптотически равна O (n) с n = окончательный размер списка. Это означает, что вся операция нажатия n объектов в списке - O (n). Если мы амортизируем это для элемента, то O (n)/n = O (1).
Временная стоимость добавления в список
Дизайнеры Python использовали очень умную идею, чтобы убедиться, что это худшее время для добавления в список происходит нечасто. Мы только что увидели, что, когда Python присоединяется к существующему списку и заканчивается в пространстве, он должен запросить новый кусок памяти, где он переместит список.
Скажем, длина списка равна n. Но вместо того, чтобы запрашивать достаточно места для списка size n + 1, Python устраивает пространство для роста нового списка и запрашивает пространство для списка size 2n. Таким образом, сглаживание таким образом может показаться, что он тратит много места. Python выделяет до twice объем памяти, который действительно нужен списку. Но преимущество заключается в том, что если вы добавляете элементы в список снова и снова, список перемещается нечасто.