Массив: элемент по адресу за O(1), сдвиг за O(n)

Коротко

Массив хранит элементы непрерывным куском памяти, одинакового размера. Поэтому адрес i-го считается арифметикой - начало + i · размер_элемента, - и «взять i-й» стоит O(1), хоть первый, хоть миллионный. Обратная сторона непрерывности: вставить или удалить в середине - значит сдвинуть весь хвост, O(n). У статического массива ещё и фиксированный размер. Динамический массив снимает ограничение размера, удваивая буфер при заполнении (амортизированный append мы доказали в прошлом разделе), но профиль остаётся тем же: индексация дёшева, сдвиг в середине дорог.

Если ты понимаешь, почему индексация массива - это O(1), а вставка в середину - O(n), и чем динамический массив отличается от статического, листай до «Теперь сам».

Как думаешь, почему массив мгновенно достаёт любой элемент

Ты пишешь a[1000000] и получаешь ответ сразу, без всякого перебора. Откуда структура знает, где лежит миллионный элемент, не проходя первый миллион? Секрет в том, КАК массив хранит данные: подряд, вплотную, элементами одинакового размера. Тогда положение i-го - не загадка, а формула. Именно эта укладка даёт массиву его сильную сторону и, как обратную сторону, слабую. Разберём обе.

На что это похоже

Многоэтажный дом с одинаковыми квартирами. Чтобы попасть в квартиру №1000, тебе не надо обходить 999 предыдущих: ты знаешь, что этажи равны, считаешь этаж = номер / 10 и едешь прямо туда. Адрес вычисляется, а не отыскивается. Но попробуй ВСЕЛИТЬ нового жильца в квартиру №5 так, чтобы номера остались подряд: всем от пятой и выше придётся переехать на квартиру вперёд. Одинаковость и порядок дают мгновенный доступ - и они же делают вставку в середину переселением всего хвоста.

Механизм: адрес - это арифметика

Массив занимает непрерывный блок памяти начиная с некоторого адреса начало. Все элементы одного размера s байт. Тогда i-й элемент лежит по адресу начало + i · s. Это одно умножение и сложение - O(1), независимо от i и от длины массива. Вот почему индексация мгновенна.

Непрерывная укладка одинаковых элементов превращает индекс в адрес - одно вычисление вместо прохода.

Обратная сторона той же укладки - вставка и удаление в середине. Чтобы вставить элемент на место i, надо освободить ячейку i: сдвинуть все элементы от i до конца на одну позицию вправо. Это до n перемещений - O(n). Удаление из середины - то же самое наоборот: хвост сдвигается влево, чтобы закрыть дырку. Порядок и непрерывность, которые дарят O(1)-доступ, требуют держать элементы вплотную - а значит платить сдвигом за любую правку не с краю.

Правило

Массив хранит элементы непрерывно, одного размера, поэтому «взять i-й» - это O(1) (адрес считается арифметикой). За тот же порядок платят сдвигом: вставка и удаление в середине - O(n), потому что хвост надо подвинуть. У статического массива размер фиксирован; динамический массив растёт, удваивая буфер, но профиль операций тот же. Массив - структура для быстрого доступа по индексу, а не для частых правок в середине.

Разбор: почему вставка в середину - это O(n)

Пусть в массиве [a, b, c, d] надо вставить x на место 1, чтобы вышло [a, x, b, c, d]. Ячейка 1 занята буквой b. Освобождаем её: d едет на место 4, c на место 3, b на место 2 - весь хвост от позиции вставки сдвигается на один вправо. Только теперь в ячейку 1 можно положить x. Сдвинули три элемента; в массиве длины n вставка у начала сдвигает почти все n - отсюда O(n). Чем ближе к началу вставка, тем длиннее сдвигаемый хвост; вставка в самый конец не сдвигает ничего и потому дёшева. Ровно это начисляет и наш тренажёр: a.insert(0, x) стоит по числу сдвинутых элементов, а a.append(x) - один шаг.

Разбор: динамический массив - это массив, который переезжает

Статический массив выделяет память один раз и не может вырасти. Динамический массив (это и есть list в Python) снимает ограничение: он держит буфер с запасом, а когда буфер заполнен, выделяет вдвое больший, копирует туда старое и продолжает. В прошлом разделе мы доказали потенциалом, что такое удвоение делает append амортизированно O(1), несмотря на редкие дорогие копирования. Но заметь: рост буфера меняет только операцию «добавить в конец». Индексация как была O(1) (память по-прежнему непрерывна), так и осталась; вставка в середину как была O(n) (сдвиг хвоста), так и осталась. Динамичность решает вопрос размера, а не профиль остальных операций.

Что ломается без этого

Главная ошибка - строить алгоритм на частой вставке или удалении в СЕРЕДИНЕ массива и удивляться квадрату. Собираешь результат, вставляя каждый новый элемент в начало списка? Каждая вставка - сдвиг всего, что уже есть, и n таких вставок дают O(n²). Массив за это наказывает, потому что непрерывность требует держать элементы вплотную. Вторая ошибка - думать, что раз массив «динамический», у него ВСЕ операции дёшевы: дёшев только append (и то амортизированно); индексация дёшева всегда, а вот правки в середине дороги независимо от того, статический массив или динамический.

Зачем это в работе

list в Python, ArrayList в Java, vector в C++, slice в Go - всё это динамические массивы, и у всех один профиль: доступ по индексу и добавление в конец - дёшево, вставка и удаление не с конца - дорого. Отсюда практические правила: собирать данные append-ом в конец, а не вставками в начало; не удалять из середины большого списка в цикле (каждое удаление - сдвиг); если нужен частый доступ по номеру - массив идеален. А когда наоборот, нужны частые вставки и удаления НЕ с конца, в дело идёт другая структура - связный список, о нём следующий урок.

Теперь сам

У тебя массив на n элементов. Ты n раз удаляешь ПЕРВЫЙ элемент (каждый раз a.pop(0)), пока массив не опустеет. Во что обойдётся вся серия и почему? Что изменилось бы, удаляй ты каждый раз ПОСЛЕДНИЙ (a.pop())?

Ответ. Удаление первого элемента сдвигает весь оставшийся хвост влево, чтобы закрыть дырку в начале: это O(длины) на каждый pop(0). Длины идут n, n−1, ..., 1, сумма n + (n−1) + ... + 1 = n(n+1)/2 = Θ(n²) - вся серия квадратична. А pop() с конца не сдвигает ничего (за удалённым элементом пусто), это O(1), и n таких удалений - всего Θ(n). Разница O(n²) против O(n) - только из-за того, с какого конца массива ты его правишь: непрерывная укладка делает конец дешёвым, а начало - дорогим.

Главное

Массив хранит элементы непрерывно и одного размера, поэтому «взять i-й» - O(1) (адрес = начало + i · размер, чистая арифметика). Плата за порядок - сдвиг: вставка и удаление в середине O(n), потому что хвост надо подвинуть; правки с конца дёшевы, с начала дороги. Статический массив фиксированного размера; динамический (list) растёт удвоением буфера, делая append амортизированно O(1), но индексацию и сдвиг это не меняет. Массив - для быстрого доступа по индексу, не для частых правок в середине.