Помогите пожалуйста понять почему в случае list (динамического массива) операция

Question

Помогите пожалуйста понять почему в случае list (динамического массива) операция

по вставке элемента в его начало имеет асимптотическую сложность O(n*n), а не O(n)?

Из эксперимента на просторах интернета это явно видно, но я не понимаю самого механизма, почему так? Если верить материалам, то для динамических массивов при вставке элемента в конец массива, в случае выхода за пределы зарезервированной памяти, все его элементы, включая тот, который вставляем, будут перезаписаны в новые ячейки памяти и тут всё ясно, сложность этого алгоритма = O(n).
Хорошо… а что меняется при вставке элемента в начало?! Ведь, если зарезервированная память переполнена, то все элементы, включая тот, который вставляем будут просто перезаписаны в новую область памяти с учётом их сдвига, откуда берётся n*n? Это возможно, если, например, сперва выделяется большая память под исходный массив, потом переписываются в неё все его элементы (O(n)), а потом все они сдвигаются чтоб освободить ячейку для первого который вставляем (опять O(n)), … но это как-то странно. Что происходит на самом деле?

#backend #programming #python #russian

0

16.05.2022

4 ответов

21 просмотр

Pavel Павлик

А откуда информация про квадратичную сложность?

0

16.05.2022

decorator-factory

Вставить один элемент в начало — это O(n). Может, ты про что-то другое?

0

16.05.2022

Alex

Потому что массив это область непрерывной памяти. Это лучше в сишке видно где элементы массива имеют последовательные адреса указателей. Соответственно чтобы вставить в начало нужно поочереди переставить все элементы

0

16.05.2022

Denis Pobedrya · Accepted Answer

Denis Pobedrya

Вставка одного элемента в начало имеет сложность O(n)

0

16.05.2022

170 похожих чатов

Помогите пожалуйста понять почему в случае list (динамического массива) операция

4 ответов

Похожие вопросы