Почему сложность по времени метода Python list.append() O(1)?
Как видно из документации по TimeComplexity, Python list Тип реализован с использованием массива.
Поэтому, если используется массив, и мы делаем несколько добавлений, в конечном итоге вам придется перераспределить пространство и скопировать всю информацию в новое пространство.
После всего этого, как это может быть O(1) худший случай?
3 ответа
Если вы посмотрите на сноску в связанном документе, вы увидите, что они содержат предупреждение:
Эти операции основаны на "Амортизированной" части "Амортизированного наихудшего случая". Отдельные действия могут занимать удивительно много времени, в зависимости от истории контейнера.
Используя амортизированный анализ, даже если нам иногда приходится выполнять дорогостоящие операции, мы можем получить более низкую оценку "средней" стоимости операций, если рассматривать их как последовательность, а не по отдельности.
Таким образом, любая отдельная операция может быть очень дорогой - O(n) или O(n^2) или что-то еще больше - но поскольку мы знаем, что эти операции редки, мы гарантируем, что последовательность операций O (n) может быть выполнена в Вовремя.
Амортизируется O (1), а не O (1).
Допустим, зарезервированный размер списка составляет 8 элементов, и он удваивается, когда заканчивается место. Вы хотите нажать 50 элементов.
Первые 8 элементов нажимают на O (1). Девятое запускает перераспределение и 8 копий, за которыми следует нажатие O (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).
Это очень просто.
Мы можем вычислить это, суммируя общее время добавления n элементов в arrayylist и разделив его на n.
Во-первых, нам нужно перемещать log (n) раз, и каждое перемещение удваивается на 2. Итак, у нас есть пропорциональный ряд, отношение которого равно 2, а длина - log (n).
Сумма пропорционального ряда равна (1-r ^ n) / (1-r). Таким образом, общее время перемещения равно (1-n)/(1-2)=n Временная сложность будет n/n=1.
Стоимость времени добавления в список
Разработчики Python использовали очень умную идею, чтобы убедиться, что это наихудшее время выполнения для добавления в список происходит нечасто. Мы только что увидели, что когда Python добавляет к существующему списку и исчерпывает пространство, он должен запросить новый кусок памяти, куда он будет перемещать список.
Допустим, длина списка равна n. Но вместо того, чтобы запрашивать достаточно места для списка size n + 1Python организует пространство для роста нового списка и запрашивает пространство для списка size 2n, Такое перераспределение может показаться так, как будто оно тратит много места - Python выделяет до twice объем памяти, который действительно нужен в списке. Но преимущество заключается в том, что если вы добавляете элементы в список снова и снова, список перемещается нечасто.