Алгоритмы с нуля
Массив
Представь ряд пронумерованных ящиков, в каждом по значению. Твой массив — это именно так: последовательность ящиков в памяти, все в ряд. Эта простота — источник мощи массива. Ящики стоят рядом, поэтому компьютер находит любой ящик мгновенно.
После этого урока ты сможешь представить массив как контигуозную память, объяснить, почему индексирование O(1), измерить стоимость операций чтения, записи, поиска, вставки, удаления и добавления, и понять, почему сила массива (быстрый доступ) и слабость (медленная вставка в середину) идут из одного факта: контигуозность.
Массив — это последовательность элементов в контигуозной (соседней) памяти. “Контигуозная” значит элементы стоят рядом: ячейка 0 по адресу 1000, ячейка 1 по адресу 1004, ячейка 2 по адресу 1008 и так далее. Каждый элемент одного размера (например, 4 байта на 32-битное число).
Почему контигуозность важна: Компьютер считает адрес любого элемента простой формулой:
адрес элемента[i] = базовый_адрес + (i × размер_элемента)Например, массив начинается по адресу 1000, каждый элемент 4 байта:
массив[0]по адресу 1000 + (0 × 4) = 1000массив[1]по адресу 1000 + (1 × 4) = 1004массив[5]по адресу 1000 + (5 × 4) = 1020
Компьютер прыгает прямо по адресу 1020, не читая другие элементы. Это O(1).
Операции с массивом и их стоимость:
-
Чтение или запись по индексу — O(1). Вычислить адрес, получить или записать значение. Готово.
-
Поиск значения — O(n). Ты не знаешь, какой индекс содержит цель, поэтому сканируешь с начала, пока не найдёшь (или не кончится массив). В худшем случае ищешь все n элементов.
1
function search(arr, target) {
2
for (let i = 0; i < arr.length; i++) {
3
if (arr[i] === target) return i;
4
}
5
return -1; // не найдено
6
}
- L2 Цикл по каждому элементу (O(n) в худшем случае)
- L3 O(1) поиск по индексу внутри цикла
-
Вставка в середину — O(n). Чтобы вставить в индекс 3, сдвигаешь все элементы с индексов 3, 4, 5, … на один шаг вправо. Если в массиве 100 элементов, сдвигаешь ~97. Сдвиг — вот стоимость.
-
Удаление из середины — O(n). То же самое: сдвигаешь все элементы после удаляемого на один шаг влево, закрыв дыру.
-
Добавление в конец (append) — O(1) амортизировано. Просто положи новый элемент в следующую свободную ячейку. Сдвигать ничего не надо (если вместимость не исчерпана, что бывает редко).
Суть: Контигуозность даёт тебе O(1) чтение, но O(n) запись в середину. Это основной трейдофф массива.
Фиксированный vs динамический массив:
Фиксированный массив имеет вместимость, установленную при создании. Когда полон, ничего не добавишь.
Динамический массив (как в JavaScript) растёт автоматически. Когда вместимость исчерпана, он выделяет больший блок, копирует все элементы, потом удаляет старый. Копирование стоит O(n), но происходит редко — только когда вместимость кончилась. Если массив каждый раз удваивает вместимость, стоимость копирования размазывается тонко по множеству добавлений. Мы говорим, что среднее время на добавление O(1) амортизировано.
Запрограммируем базовые операции с массивом:
O(1) индексирование:
function get(arr, i) {
return arr[i]; // Мгновенно: вычислить адрес, вернуть значение
}O(n) линейный поиск:
function search(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1; // не найдено
}O(n) вставка на индекс i:
function insertAt(arr, i, value) {
// Сдвинуть все элементы с индекса i и далее на один шаг вправо
for (let j = arr.length - 1; j >= i; j--) {
arr[j + 1] = arr[j];
}
// Поместить новое значение
arr[i] = value;
}Цикл сдвига идёт с конца назад (чтобы не перезаписать). Для массива из 100 элементов вставка на индекс 0 сдвигает все 100. Для 1000 элементов — все 1000. Это O(n).
Попробуй вызвать эти функции:
Посмотри функцию insertAt пошагово. Вставляем значение 25 на индекс 2 в массив [10, 20, 30, 40]:
1
function insertAt(arr, i, value) {
2
for (let j = arr.length - 1; j >= i; j--) {
3
arr[j + 1] = arr[j];
4
}
5
arr[i] = value;
6
}
Таблица временной сложности операций с массивом:
| Операция | Пример | Время |
|---|---|---|
| Получить элемент | arr[5] | O(1) |
| Установить элемент | arr[5] = 99 | O(1) |
| Поиск значения | search(arr, 99) | O(n) |
| Вставить на индекс i | insertAt(arr, 2, 50) | O(n) |
| Удалить на индексе i | deleteAt(arr, 2) | O(n) |
| Добавить в конец (push) | arr.push(99) | O(1) амортизировано |
Почему append O(1) амортизировано? В динамическом массиве добавление бесплатно, пока есть свободная вместимость. Когда вместимость кончилась, массив удваивает размер и копирует все n элементов (O(n) работы). Но это происходит редко — один раз на каждые n добавлений. Распределённая по n операциям, стоимость копирования в среднем O(1) на добавление.
Основная идея: Случайный доступ дёшев. Последовательная модификация дорога. Это делает массивы идеальными для операций с читаем и ужасными для частых вставок в середину.
Массив из 1000 элементов начинается по адресу 2000 в памяти. Каждый элемент занимает 8 байт. Какой адрес у элемента массив[10]?
Почему чтение массив[i] всегда O(1), даже для очень больших массивов?
Ты хочешь вставить элемент на индекс 0 в массив из 500 элементов. Сколько элементов должно сдвинуться?
Что значит 'амортизировано O(1)' для добавления в динамический массив?
Расставь эти операции с массивом от быстрейшей к медленнейшей (от лучшей к худшей сложности):
- Добавить в конец (динамический массив)
- Прочитать элемент по индексу
- Найти значение
- Вставить в начало
Граничные случаи
Фиксированные массивы кончаются. Если массив вместит 4 элемента, а ты пытаешься добавить 5-й, получишь ошибку или потеряешь элемент (в языке, как C). JavaScript массивы всегда динамические — они молча растут. Но рост не бесплатен; он стоит O(n) работы. Поэтому добавление “амортизировано” O(1), а не всегда O(1).
Частая ошибка
Путаешь размер массива и стоимость. Вставить в массив из 10 элементов намного быстрее, чем в массив из 1 миллиона. Но оба случая “O(n)”. Не думай, что O(n) значит “время не важно”; это значит время растёт пропорционально n. На 1 миллион элементов ты реально сдвинешь 1 миллион раз.
Почему контигуозность массива (элементы в соседней памяти) даёт ему и силу, и слабость?
Массив — это ряд контигуозных ячеек памяти, все одного размера.
Ключевые факты:
- Контигуозная память: Элементы лежат рядом, позволяя вычислить адрес:
база + (индекс × размер_элемента). - O(1) чтение и запись: Получить или изменить элемент по индексу за постоянное время — без сканирования.
- O(n) поиск: Найти значение нужно сканировать элементы один за другим (худший случай: все n).
- O(n) вставить/удалить в середину: Надо сдвинуть все элементы после изменения, линейно в худшем случае.
- O(1) амортизировано добавить: Бесплатно большую часть времени; редко вызывает resize, стоимость размазана.
- Трейдофф: Контигуозность даёт быстрый доступ, но медленную модификацию. Выбери массивы для операций, где много чтения.
Дальше ты узнаешь приёмы, что используют это знание: как быстрее искать (бинарный поиск), как быстрее менять (два указателя, скользящее окно), и когда использовать другие структуры (списки, очереди) вместо массива.