Сложность описывает, как растёт время или память с ростом входных данных. O(n) на миллионе элементов — миллисекунды, O(n²) — минуты.
Что важно знать
- Оценивать сложность своего кода: вложенный цикл по тем же данным — O(n²), поиск в хеш-таблице — O(1) в среднем, сортировка — O(n log n).
- Сортировки: как работают быстрая и слиянием, почему нижняя граница сравнивающих сортировок — n log n, что такое устойчивость. Встроенная сортировка языка почти всегда лучше своей.
- Бинарный поиск по отсортированным данным — O(log n), и его вариации («первый элемент не меньше x»).
- Два указателя, скользящее окно, префиксные суммы — приёмы, которые закрывают большую часть задач с массивами и строками.
- Рекурсия и мемоизация, основы динамического программирования.
- Графы: обход в ширину и в глубину, кратчайший путь.
Как готовиться
Решать задачи регулярно — 2–3 в неделю лучше, чем 50 перед собеседованием. Проговаривать решение вслух: на секции оценивают и рассуждение, и код, и проверку на граничных случаях.