Сегодня, читая о временных сложностях, я решил сосредоточиться на том, как 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).
Просто к сведению: динамические массивы, которые удваивают размер в два раза, немного быстрее.