Массив
Массив — это ряд ячеек в памяти, в каждой ячейке одно значение. Ячейки стоят рядом (контигуозны), поэтому ты можешь прыгнуть в любую за O(1). Поняв это, ты поймёшь стоимость каждой операции: чтение/запись O(1), поиск O(n), вставка в середину O(n).
Представь ряд пронумерованных ящиков, в каждом по значению. Твой массив — это именно так: последовательность ящиков в памяти, все в ряд. Эта простота — источник мощи массива. Ящики стоят рядом, поэтому компьютер находит любой ящик мгновенно. За десять минут ты будешь знать, почему именно этот один факт определяет цену каждой операции с массивом.
После этого урока ты сможешь представить массив как контигуозную память, объяснить, почему индексирование 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 элементов.
function search(arr, target) { for (let i = 0; i < arr.length; i++) { if (arr[i] === target) return i; } return -1; // не найдено } - 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]:
function insertAt(arr, i, value) { for (let j = arr.length - 1; j >= i; j--) { arr[j + 1] = arr[j]; } arr[i] = value; } Таблица временной сложности операций с массивом:
| Операция | Пример | Время |
|---|---|---|
| Получить элемент | 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, стоимость размазана.
- Трейдофф: Контигуозность даёт быстрый доступ, но медленную модификацию. Выбери массивы для операций, где много чтения.
Дальше ты узнаешь приёмы, что используют это знание: как быстрее искать (бинарный поиск), как быстрее менять (два указателя, скользящее окно), и когда использовать другие структуры (списки, очереди) вместо массива. Теперь, когда ты увидишь код, который вставляет элементы в середину массива в плотном цикле, ты сразу опознаешь это как O(n²) и потянешься к лучшей структуре данных.
Практика
Начни сверху. Задачи идут от простого к сложному: вспомнить факт, применить к случаю, затем senior-уровень. Открой, попробуй, потом открой ответ.
Что-то непонятно?
Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.
Примени это
Примени этот урок в реальном проекте.