Сегодня, читая о временных сложностях, я решил сосредоточиться на том, как python работает внутри. Это привело меня к сложностям амортизации времени и к тому, как "список" Python вычисляет операции вставки и удаления за время O (1).

Если вы знакомы с python, вы должны знать, что python позволяет создавать список, не определяя его длину при инициализации. В большинстве языков программирования, таких как Java, C / C ++ и т. Д., Необходимо указать длину массива.

Так как же Python удается создать список без явного указания его длины? Это массив бесконечной длины?

Списки - это не массивы с бесконечным хранилищем.

Как мы все знаем, сложность вставки элемента в список во время выполнения составляет O (1) раз. Означает ли это, что список имеет бесконечное количество блоков памяти? Массив бесконечного размера был бы дорогостоящим с точки зрения вычислений. Представьте, что ваша система предоставляет списку большие объемы хранилища, чтобы в нем никогда не кончалось хранилище.

«Список» Python - это структура данных, подобная массиву, которая предлагает динамическое изменение размера.

Список изменяет свой размер по мере необходимости, при этом обеспечивая доступ O (1). В большинстве языков программирования это достигается удвоением размера массива при заполнении. Например, длина динамического массива для большинства языков программирования будет выглядеть следующим образом.

Временная сложность копирования n элементов в новый массив будет O (n)

Поскольку это происходит только в редких случаях, то есть при изменении длины массива, сложность вставки в наихудшем случае составляет O (n).

Итак, какова будет средняя временная сложность прошивок

Давайте посчитаем временную сложность добавления n объектов в динамический массив.

Временная сложность для добавления n объектов в динамический массив будет во всех случаях, когда временная сложность просто O (1) (добавляет), и все эти редкие события, когда временная сложность равна O (n) (копия)

Таким образом, временная сложность может быть записана следующим образом

Средняя стоимость вставки ’n’ объектов в динамический массив составляет O (n), и, следовательно, средняя стоимость одной вставки составляет O (1).

Теперь мы можем сказать, что добавление элемента выполняется за O (n), то есть в среднем за линейное время. Это называется амортизированной временной сложностью. Таким образом, способ анализа всей операции (вставка n объектов) вместо одной только операции называется амортизированным анализом.

Изменение размеров списков в Python

Я написал следующий код, чтобы проверить, где список Python удваивается. Код добавляет 100 объектов в список и вычисляет его размер (который помогает определить длину динамического массива) на каждом шаге.

Как мы видим, List list_ меняет свой размер на i = 0,1,5,9,17,26,… Это не то же самое, что уравнение удвоения, когда длина массива достигает степень двойки. Уравнение для Python имеет следующий вид:

length = ceil (1,125 * n + 3), когда n ≥1 && n ‹9

length = ceil (1,125 * n + 6) при n ≥9

Это уравнение применяется только при n ›длине списка, т.е. при n = 1, 5,9,17, .. с новыми значениями 5,9,17, 26,…

Итак, какова будет средняя временная сложность прошивок

Подобно приведенному выше уравнению, временная сложность для добавления n объектов в динамический массив будет во всех случаях, когда временная сложность равна просто O (1) (добавляет), и все эти редкие события, когда временная сложность O (n) (копия)

Временную сложность можно записать следующим образом

Я попытался решить вторую часть уравнения и не смог найти конкретного математического доказательства, не предполагая, что Ceil (x) ~ x. Итак, запустили моделирование вышеупомянутой операции.

Я построил ряд «n» против Sum os для n Graph

Вторая часть уравнения приблизительно сходится к 10 * n. Что делает нашу временную сложность для вставки в список O (11n), что является не чем иным, как O (n) временем для вставки n объектов.

По амортизированному анализу list.append в Python принимает O (1).

Просто к сведению: динамические массивы, которые удваивают размер в два раза, немного быстрее.