Карта раздела для новичка
На этой странице
Начинать стоит не с сортировок, а с того, как читать задачу и проверять решение руками. Дальше - Big O, базовые структуры данных, поиск и сортировка, паттерны, деревья и графы, рекурсия и DP. Этот урок - маршрут по разделу и словарь английских терминов, которые встречаются в каждом уроке.
Вопрос
С чего начать изучение алгоритмов и в каком порядке проходить раздел?
Как устроен раздел
Уроки разделов 01-08 короткие: в них главная идея, код, сложность и ответ для собеседования. Раздел 09 написан подробнее, специально для новичка: в нем процесс решения задач и темы, которые в основной части не поместились.
Если вы только начинаете, идите по маршруту ниже, а не по номерам папок.
Маршрут
Шаг 1. Как вообще решать задачи
- Как новичку читать алгоритмическую задачу
- Как делать dry run - ручная трассировка понадобится в каждом следующем уроке.
Шаг 2. Сложность
- Что такое алгоритм
- Big O notation, затем остальные уроки темы База и сложность алгоритмов.
Шаг 3. Инструменты JavaScript и линейные структуры
- Array, Map, Set.
- Тема Линейные структуры данных: array, linked list, stack, queue, hash table, heap.
- Как выбирать структуру данных под задачу - связывает все предыдущее.
Уроки про TypeScript и generics можно отложить: они полезны, но не обязательны для понимания алгоритмов.
Шаг 4. Поиск и сортировка
- Тема Поиск и сортировка по порядку.
- Как избегать off by one - сразу после binary search.
Шаг 5. Паттерны
- Как превращать brute force в оптимальное решение - объясняет, зачем паттерны вообще нужны.
- Тема Паттерны решения задач: two pointers, sliding window, prefix sums, hash map, intervals, monotonic stack, fast/slow pointers, backtracking.
- Как доказывать корректность через инварианты.
Шаг 6. Деревья, графы, рекурсия и DP
- Как работает рекурсия - ее лучше понять до деревьев.
- Тема Деревья и графы, затем Matrix и grid.
- Остальная тема Рекурсия, DP и greedy.
Шаг 7. Дополнительные темы
Шаг 8. Подготовка к собеседованию
- Тема Практика и собеседования: процесс решения, разговор о сложности, список задач и план подготовки.
Как проходить урок
- Прочитайте идею и код.
- Повторите трассировку из урока на бумаге, не подглядывая.
- Перепишите код сами в песочнице и запустите на своих примерах, включая пустой input.
- Решите 1-2 задачи на этот паттерн (список - в уроке Какие задачи нужно уметь решать).
- Через несколько дней вернитесь к карточке урока и ответьте на вопрос вслух.
Словарь терминов
В уроках много английских слов: так говорят на собеседованиях и так называются задачи на LeetCode. Основные:
| Термин | Что значит |
|---|---|
| input / output | входные данные / результат функции |
| constraints | ограничения из условия: размер n, диапазон чисел |
| edge case | крайний случай: пустой массив, один элемент, отрицательные числа |
| happy path | "обычный" вход, на котором все работает |
| brute force | решение "в лоб", перебором |
| baseline | простое правильное решение, с которым сравнивают оптимизацию |
| dry run, trace | ручной прогон алгоритма по шагам |
| time / space complexity | сколько времени / дополнительной памяти нужно в зависимости от n |
| auxiliary space | дополнительная память без учета input и output |
| amortized | "в среднем на операцию" с учетом редких дорогих операций |
| best / average / worst case | лучший / средний / худший вариант входных данных |
| in-place | алгоритм меняет исходный массив и почти не берет память |
| mutate | изменять исходные данные |
| stable sort | сортировка, сохраняющая порядок равных элементов |
| comparator | функция сравнения (a, b) => number для sort |
| pivot | опорный элемент в quick sort |
| pointer | индекс или ссылка, которую двигают по данным |
| window | непрерывный кусок массива [left, right] |
| prefix | начало массива или строки |
| contiguous | идущий подряд, без пропусков |
| subarray / substring | непрерывный кусок массива / строки |
| subsequence | элементы в том же порядке, но не обязательно подряд |
| node, vertex | узел, вершина |
| edge | ребро, связь между вершинами |
| root / leaf | корень / лист (узел без детей) дерева |
| visited | множество уже посещенных вершин |
| adjacency list | список соседей для каждой вершины |
| directed / weighted | ориентированный граф / граф с весами на ребрах |
| DAG | ориентированный граф без циклов |
| base case | случай, когда рекурсия останавливается |
| memoization | кеш ответов уже решенных подзадач |
| DP, state, transition | динамическое программирование; что хранит ячейка; как она считается |
| greedy | жадный алгоритм: берет лучший вариант прямо сейчас |
| invariant | утверждение, которое верно на каждом шаге алгоритма |
| pruning | отсечение веток перебора, которые точно не дадут ответ |
| trade-off | компромисс: например, больше памяти ради скорости |
| off-by-one | ошибка на единицу в индексах или границах |
Что отвечать на собеседовании?
Если спрашивают, как готовиться к алгоритмам, хороший ответ такой: сначала нужно понять базовые структуры данных и Big O, затем научиться разбирать задачу: вход, выход, ограничения, примеры, edge cases. После этого решают brute force, ищут повторную работу, подбирают структуру данных или паттерн, делают dry run, доказывают корректность через инвариант и только потом пишут код.
Мини-шпаргалка
- Начинайте с чтения задачи и dry run, а не с сортировок.
- Каждую задачу начинайте с input/output/constraints.
- Делайте dry run до и после кода.
- Структура данных выбирается по операции, которую нужно ускорить.
- Brute force - полезная стартовая точка.
- Корректность объясняется инвариантом или свойством паттерна.
- Незнакомый термин - смотрите словарь в этом уроке.
Документация
NeetCode Roadmap, VisuAlgo - анимации структур данных и алгоритмов.