Массивы: Фундамент структур данных

Цели урока

• Понять, как массив хранится в памяти (contiguous)
• Объяснить, почему доступ O(1), а вставка O(n)
• Различать статические и динамические массивы
• Знать, когда массив - правильный выбор

Предварительные знания

• Базовая работа со списками в Python

• Массивы и списки

Почему доступ к элементу массива мгновенный, а вставка в середину - медленная? Ответ не в алгоритмах, а в устройстве памяти.

• **FAANG интервью**: половина задач - массивы (two pointers, sliding window, prefix sum)
• **90% структур данных** используют массивы внутри: хеш-таблицы, кучи, графы
• **Cache locality**: массивы дружат с кэшем CPU → реальная скорость в разы выше

Массив - старейшая структура данных

Массив старше почти всех остальных структур данных, потому что он напрямую отражает устройство памяти: непрерывный блок ячеек с последовательными адресами. Первым языком высокого уровня с настоящими массивами стал FORTRAN, выпущенный командой Джона Бэкуса в IBM в 1957 году. Индексация и многомерные массивы были там центральной фичей, ведь язык создавался для научных и инженерных расчётов. В 1962 году Кеннет Айверсон в книге A Programming Language (язык APL) сделал массив главным объектом вычислений: целые операции выполнялись над массивами целиком, без явных циклов. Эта идея позже легла в основу NumPy и MATLAB. В 1972 году Деннис Ритчи в языке C закрепил связь массива и указателя: запись arr[i] эквивалентна *(arr + i), и именно эта арифметика адресов даёт O(1) доступ, который мы изучаем.

Память как улица с домами

Представь, что память компьютера - это **бесконечная улица с пронумерованными домами**. Каждый дом имеет адрес: 0, 1, 2, 3...

Массив - это **бронь подряд идущих домов**. Если тебе нужно 5 элементов, ты бронируешь дома 100, 101, 102, 103, 104. Они идут **непрерывно** (contiguous).

**Ключевой инсайт:** Зная начальный адрес (100) и индекс (i), компьютер **мгновенно** вычисляет, где лежит элемент: `100 + i`. Никакого поиска!

O(1) доступ - суперсила массива

Благодаря непрерывному расположению, массив даёт **random access** (произвольный доступ) за **O(1)** - константное время.

**O(1)** означает: неважно, миллион элементов в массиве или миллиард - доступ к любому занимает **одинаковое время**. Просто арифметика: `base + index`.

Вставка: Почему O(n)?

Вот и **обратная сторона медали**. Чтобы вставить элемент в середину, нужно **подвинуть всех соседей**.

**Худший случай:** вставка в начало. Нужно сдвинуть **все n элементов**. Это **O(n)**.

**Лучший случай:** вставка в конец. Сдвигать никого не надо. Это **O(1)** (если есть место).

Статические vs Динамические массивы

В классических языках (C, C++) массив имеет **фиксированный размер**. Объявил `int arr[10]` - всё, ровно 10 ячеек, ни больше, ни меньше.

**Динамические массивы** (Python list, Java ArrayList, C++ vector) **растут автоматически**. Как?

**Amortized O(1):** Хотя редко бывает копирование всех элементов (O(n)), в среднем добавление в конец - O(1). Почему? Потому что capacity удваивается, и копирование происходит всё реже.

Сводная таблица сложности

Теперь ты понимаешь, **почему** у массива такие сложности, а не просто заучил таблицу.

**Когда использовать массив:**

• ✅ Нужен быстрый доступ по индексу
• ✅ Данные редко вставляются/удаляются в середине
• ✅ Известен примерный размер заранее

**Когда НЕ использовать:**

• ❌ Частые вставки/удаления в начало
• ❌ Размер сильно колеблется

**Помнишь вопрос из начала?** Почему Netflix может хранить миллионы фильмов и мгновенно находить любой по ID? Потому что ID - это индекс, а доступ по индексу - O(1). Арифметика вместо поиска.

Анализ сложности Определи сложность каждой операции: ```python arr = [1, 2, 3, 4, 5] # Операция 1 x = arr[2] # Операция 2 arr.append(6) # Операция 3 arr.insert(0, 0) # Операция 4 for item in arr: print(item) ```

# Операция 1: O(1) - доступ по индексу # Операция 2: O(1) amortized - вставка в конец # Операция 3: O(n) - вставка в начало, сдвиг всех # Операция 4: O(n) - проход по всем элементам

Оптимизация алгоритма Этот код неэффективен. Почему? Как исправить? ```python def build_list_badly(n): result = [] for i in range(n): result.insert(0, i) # Вставляем в начало return result # При n = 100,000 работает очень медленно! ```

def build_list_well(n): result = [] for i in range(n): result.append(i) # O(1) вместо O(n) result.reverse() # Один проход O(n) return result # Или ещё проще: def build_list_pythonic(n): return list(range(n-1, -1, -1))

Выбор структуры данных Для каждого сценария определи: подходит ли массив? Почему? 1. **Лента Instagram**: показ постов сверху вниз, подгрузка новых сверху 2. **Рейтинг игроков**: топ-100, доступ по месту (1st, 2nd, 3rd...) 3. **Undo/Redo в редакторе**: последнее действие отменяется первым 4. **Кэш браузера**: быстрый доступ к странице по URL

# 1. Лента Instagram # ❌ Массив не идеален # Новые посты вставляются в начало - O(n) # Лучше: deque или связный список # 2. Рейтинг игроков # ✅ Массив идеален # Доступ по индексу (месту) - O(1) # Изменения редки # 3. Undo/Redo # ✅ Массив (как стек) # Добавление/удаление только с конца - O(1) # Стек - это массив с ограниченным интерфейсом # 4. Кэш браузера # ❌ Массив не подходит # Нужен поиск по ключу (URL), не по индексу # Лучше: хеш-таблица (dict)

Куда дальше?

Массив - фундамент. Вот что строится на нём:

• Связные списки — Решают проблему O(n) вставки ценой O(n) доступа
• Хеш-таблицы — Массив + хеш-функция = O(1) поиск по ключу
• Алгоритмы сортировки — Большинство алгоритмов сортировки работают с массивами

Ключевые идеи

• **Массив** - непрерывный блок памяти с O(1) доступом по индексу
• **Вставка/удаление** из середины - O(n) из-за сдвига элементов
• **Динамические массивы** растут x2, давая amortized O(1) append
• **Выбор структуры** зависит от частых операций, не от "моды"
• **Netflix находит профиль** за микросекунды потому что ID = индекс = O(1)

Вопросы для размышления

• Почему Python list - это динамический массив, а не связный список?
• Какие операции были бы быстрее/медленнее со связным списком?
• Помнишь вопрос из начала про Netflix? Теперь понимаешь, как это работает?

Связанные уроки

• prog-11-arrays — Базовые массивы в программировании - предпосылка для понимания их внутреннего устройства
• alg-01-big-o — Big O нотация нужна для понимания O(1) vs O(n) операций массива
• ds-02-linked-lists — Связные списки - прямая альтернатива массивам с разными компромиссами
• arch-01-binary — Адресация памяти компьютера - физическая основа концепции массива
• arch-08-memory-hierarchy