Алгоритмы: Big-O, структуры и базовые паттерны

Серия 02 CS открывает алгоритмическую под-серию из трёх уроков. Этот первый закрывает фундамент, на который будут опираться графы, парадигмы и production-структуры. После него ты читаешь Big-O без шпаргалки, выбираешь между списком, мапой и кучей по двум вопросам, и видишь “два указателя” и “хеш-мап за один проход” не как трюки, а как два рабочих инструмента из ста.

Стиль урока, как у Бхаргавы в “Грокаем алгоритмы”. Сначала бытовая сцена и картинка, потом идея словами, и только потом код. Если к разделу есть виджет, сцена закрывается им до первого function.

Сцена · почему алгоритмы вернулись

Ты можешь работать пять лет, ни разу не написав свою сортировку. И всё же три ситуации возвращают алгоритмы из ниоткуда. Первая, собес: тебе дают n = 100000, наивный O(n²) валится по таймауту, и нужно за пятнадцать минут увидеть, какой шаг лишний. Вторая, продакшн-инцидент: запрос внезапно стал отвечать минутами, и причина не в базе, а в квадратичном цикле, который вырос вместе с данными. Третья, выбор структуры под задачу: “взять массив или мапу” звучит безобидно, пока очередь сообщений не превратится в splice на каждый ack.

Эта серия про то, как такие моменты перестают быть откровением. Сегодня мы кладём фундамент.

Карта урока · что заберёшь домой через 210 минут

Через три с половиной часа у тебя в голове будет:

• Big-O за 15 минут, без таблиц и без зубрёжки. Просто чувство кривой, которой ты подчиняешься, когда жмёшь Run.
• Семь базовых структур: Array, LinkedList, Stack, Queue, Deque, HashTable, BST. Плюс HashMap, которую мы соберём своими руками, чтобы collision-resolution не звучал как заклинание.
• Линейный и двоичный поиск, с инвариантом, по которому бинарный поиск не ломается на границах.
• Четыре сортировки в одной гонке: bubble, insertion, merge, quick. TimSort одной выноской, потому что именно её ты и зовёшь, когда пишешь Array.prototype.sort.
• Два рабочих паттерна на десятке задач: “два указателя” и “один проход плюс хеш-мап”. Этих двух хватает, чтобы закрыть половину раздела Arrays and Hashing в NeetCode.

В конце финальный чек-лист и ДЗ на четыре пункта. Дальше урок 10 берёт ту же оптику и перекладывает её на графы и парадигмы.

Раздел 1 · Бинарный поиск как игра “угадай число”

Сцена

Ты загадываешь число от 1 до 100. Я угадываю за семь шагов, всегда. Не потому что у меня хорошее чутьё, а потому что я не угадываю, я половиню. Назвал 50, ты сказал “больше”, значит ответ в [51, 100], половина пространства отрезана за один вопрос. Назвал 75, ты сказал “меньше”, ответ в [51, 74], отрезана половина того, что осталось. И так далее, пока интервал не сожмётся до одной точки.

То же самое делает бинарный поиск в отсортированном массиве: на каждом шаге смотрит на средний элемент и выбрасывает половину, в которой ответа точно нет. Из миллиона элементов он находит нужный за двадцать шагов, не за миллион.

Идея словами

У тебя три указателя: lo, hi, mid. Инвариант: ответ всегда лежит в полуинтервале [lo, hi]. Шаг алгоритма не нарушает этот инвариант. Цикл заканчивается, когда lo > hi, и в этот момент ответа в массиве нет. Всё. Бинарный поиск это один маленький инвариант плюс цикл, который его сохраняет.

03

17

211

314

422

527

635

741

849

955

1062

1168

1273

1381

1488

1594

0lo15hi?mid0сравненийготовстатус

Двигай ползунок и жми шаг. На каждом шаге mid делит отрезок пополам, и одна половина выпадает из поиска. Заметь, что цель либо находится за log2(16) = 4 сравнения, либо отрезок схлопывается до пустого, и поиск возвращает minus один.

Что взять с собой

• Бинарный поиск работает только на отсортированных данных. Без сортировки заранее, его сложность подразумевает скрытую цену сортировки сверху.
• Сложность времени, O(log n). Памяти, O(1) для итеративной версии, O(log n) для рекурсивной из-за стека вызовов.
• Самая частая ошибка, неверная граница (< против <=) и переполнение на (lo + hi) / 2. Лекарство, всегда проговаривать инвариант вслух.
• Близкие родственники, Array.prototype.findIndex (линейный по умолчанию) и binary search on answer, к которому мы вернёмся в уроке 11.

Инвариант проверяется руками, а не на словах. Напиши две границы поиска и посмотри, где именно < отличается от <=.

Раздел 2 · Хеш-таблица как телефонная книга

Сцена

В бумажной телефонной книге ты не листаешь все страницы по очереди. Ты открываешь книгу примерно на букве “К”, потому что фамилия начинается на “К”, и за один шаг попадаешь близко к нужной странице. Хеш-таблица устроена так же. Ключ прогоняется через хеш-функцию, она возвращает индекс корзины, и значение лежит ровно там. Доступ за один шаг.

Загвоздка одна, разные ключи иногда отображаются в одну корзину. Это называется коллизия. Способов её разрешить ровно два: класть в корзину список (chaining) или искать первую свободную соседнюю корзину (open addressing). Оба способа работают, у обоих свои особенности.

Идея словами

Хеш-таблица состоит из трёх частей. Массив корзин фиксированного размера, хеш-функция, которая ключ превращает в индекс, и стратегия разрешения коллизий. Когда корзин становится мало (load factor выше порога), таблица растёт: создаёт массив побольше и переразмещает все ключи заново. Это rehashing, и именно из-за него средняя стоимость insert остаётся O(1), хоть отдельный insert иногда платит за всех.

Хеш-функция для пользовательских ключей, отдельная тема. На уроке мы возьмём простую: сумма char-кодов по модулю размера массива. В реальной библиотеке это будет MurmurHash или FNV-1a. Атака HashDoS, когда злоумышленник специально подбирает ключи с одной и той же корзиной, лечится рандомизацией seed-а хеш-функции на старте процесса.

Что взять с собой

• Вставка, поиск, удаление: амортизированно O(1), в худшем случае O(n), если все ключи попали в одну корзину.
• Память: O(n) плюс накладные расходы на корзины. Map в JS даёт вставку и удаление за O(1) без неожиданных гонок с прототипом, в отличие от обычного объекта.
• Когда брать Map, а не объект: ключи не строки, нужно сохранить порядок вставки, важен метод .size. В остальных кейсах объект быстрее на горячем коде, потому что V8 оптимизирует hidden classes.
• Когда брать Set: дедуп, проверка принадлежности за O(1). Не путать с WeakSet, который не держит сильную ссылку и нужен ровно для памяти-чувствительных кешей.

Раздел 3 · Шкафы и башни: семь базовых структур

Сцена

Структуры данных проще запомнить картинкой, чем списком. Стек, башня тарелок: положил сверху, снял сверху. Очередь, очередь к кассе: пришёл последним, ушёл последним. Двусторонняя очередь, лента в магазине: можно зайти с любой стороны и выйти с любой. Связный список, цепочка вагонов: у каждого вагона ссылка на следующего, чтобы добраться до седьмого, надо пройти первые шесть.

Дерево решений в твоей голове, бинарное дерево. Турнирная сетка плей-офф, куча. Алфавитное оглавление словаря, префиксное дерево (Trie). Карта московского метро, граф. Каждая структура отвечает на один-два вопроса, которые она умеет решать быстрее остальных.

Идея словами

Семь базовых структур, на которых стоит остальной курс:

1. Array. Случайный доступ за O(1). Вставка и удаление в середине, O(n). Хранится непрерывным куском памяти, отлично дружит с кешем процессора (почему это важно, разобрано в уроке про машину). Под капотом массив JS, это динамический массив (вектор): движок держит запас capacity, и когда место кончается, выделяет новый кусок в 1.5-2 раза больше и копирует элементы. Само копирование стоит O(n), но случается оно так редко, что в среднем push остаётся амортизированным O(1). Та же арифметика у роста хеш-таблицы из раздела 2.
2. LinkedList. Цепочка узлов через ссылки. Вставка и удаление в произвольном месте за O(1), если узел уже у тебя в руках. Доступ по индексу, O(n). Хранится по разным адресам, кеш процессора не радуется. Односвязный и двусвязный, разные звери: двусвязный даёт удаление узла за O(1) без знания предшественника.
3. Stack. LIFO. Push, pop, peek за O(1). Реализуется массивом или списком. Когда нужен: парсеры, обход дерева, undo-стек, рекурсия в итерации.
4. Queue. FIFO. Enqueue и dequeue за O(1). Реализуется кольцевым буфером или двумя стеками. Когда нужен: BFS, очереди задач, producer/consumer.
5. Deque. Очередь с двух концов. Покрывает оба паттерна выше плюс скользящее окно. В JS реализуется массивом, но внимание, Array.shift стоит O(n). Для серьёзной работы берут @datastructures-js/deque или собирают свой кольцевой буфер.
6. HashTable. Подробно в разделе 2.
7. Binary Search Tree. Вставка, поиск, удаление в среднем за O(log n), в худшем за O(n), если дерево выродилось в цепочку (а вырождается оно буднично: вставь отсортированные данные, и каждый узел уйдёт вправо). Балансировка (AVL, Red-Black) держит высоту логарифмической ценой небольшого оверхеда на каждой операции. Механика лечения одна: ротация, локальный поворот тройки узлов, который укорачивает тяжёлую сторону, не ломая порядок. AVL после каждой вставки проверяет, что высоты поддеревьев расходятся максимум на 1, и поворачивает сразу: дерево ниже, поиск быстрее, вставка дороже. Red-Black допускает перекос до двух раз, красит узлы и поворачивает реже: вставка дешевле, поиск чуть длиннее. Поэтому AVL выбирают для read-heavy словарей, а Red-Black живёт в std::map и планировщике Linux. В реальном продакшене ты редко пишешь BST руками: за тебя это уже делает индекс в Postgres (B-Tree, который ты соберёшь сам) или sorted set в Redis (Skip List).

Плюс куча (Heap) для приоритетных очередей и Trie для префиксного поиска. Они появятся подробно в уроке 11, здесь только оставляем точку входа.

Упражнения

Что взять с собой

• Структура выбирается под две вещи: какой паттерн доступа у тебя самый частый, и сколько памяти ты готов тратить.
• Если массив сделал тебе плохо, обычно виноваты splice, unshift или shift в горячей точке. Это O(n), а ты ждал O(1).
• Linked list в современном JS, нишевая структура. Чаще всего его роль играет специализированная структура: deque, ring buffer, LRU.
• “Когда взять что”, таблица в шпаргалке внизу урока 11. Сегодня важно понять, что выбор есть и что у каждой структуры есть один-два бронебойных применения.