Big-O: оценка сложности
Big-O — математическая оценка скорости роста времени работы и памяти алгоритма при увеличении n. Это абстрактная характеристика, а не измерение в секундах: O(1) — константа, O(n) — линейный рост, O(n²) — квадратичный. На собеседовании интервьюер ждёт Big-O до написания кода — это показывает, что вы понимаете масштаб задачи.
Когда применять / Мотивация
Заголовок раздела «Когда применять / Мотивация»Big-O — обязательный язык на алгоритмическом собесе и в ежедневной работе Senior разработчика. Если n ≤ 100, даже O(n³) пройдёт. Если n = 10⁶, реалистичны только O(n) и O(n log n). В продакшене это критично: алгоритм O(n²) при миллионах запросов убьёт сервер, O(log n) — будет летать.
Реальные примеры выбора по Big-O:
- Индекс БД: B-tree O(log n) для range queries vs hash O(1) для точных ключей vs full scan O(n).
- Кэш: LRU требует O(1) на операцию — нужны hash + doubly-linked list.
- Стандартные библиотеки:
Array.sortв JS — Timsort O(n log n) среднее, но устойчивая. - Redis sorted sets: skip list O(log n) vs AVL O(log n) — выбрали skip list за простоту реализации при той же асимптотике.
Идея / Как работает
Заголовок раздела «Идея / Как работает»Big-O игнорирует константы и младшие члены: O(3n² + 5n + 10) упрощается до O(n²), потому что при больших n доминирует n². Иерархия классов:
O(1) < O(log n) < O(√n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)При n = 10⁶:
- O(log n) ≈ 20 операций
- O(n) = 10⁶
- O(n log n) ≈ 2·10⁷
- O(n²) = 10¹² (часы вместо секунд)
Различаем:
- Worst-case — наихудший случай (гарантия).
- Average-case — усреднение по случайным входам.
- Amortized — усреднение по последовательности операций. Например,
Array.pushв JS — O(1) amortized, но иногда O(n) при расширении буфера.
Реализация
Заголовок раздела «Реализация»Сравним Linear Search и Binary Search на отсортированном массиве nums = [1, 3, 5, 7, 9, 11, 13, 15], цель target = 5.
Linear Search O(n)
Заголовок раздела «Linear Search O(n)»function linearSearch(nums: number[], target: number): number { for (let i = 0; i < nums.length; i++) { if (nums[i] === target) return i; } return -1;}Время O(n) — в худшем случае проверяем все элементы. Память O(1).
Binary Search O(log n)
Заголовок раздела «Binary Search O(log n)»function binarySearch(nums: number[], target: number): number { let left = 0, right = nums.length - 1; while (left <= right) { // Защита от переполнения: left + (right - left)/2 вместо (left + right)/2 const mid = left + Math.floor((right - left) / 2); if (nums[mid] === target) return mid; if (nums[mid] < target) left = mid + 1; else right = mid - 1; } return -1;}Время O(log n) — каждый шаг делит область пополам. Память O(1) для итеративной версии (O(log n) для рекурсивной из-за стека).
Трассировка Binary Search
Заголовок раздела «Трассировка Binary Search»nums = [1,3,5,7,9,11,13,15], target=5left=0, right=7Шаг 1: mid=3, nums[3]=7 > 5 → right=2, область [0..2]Шаг 2: mid=1, nums[1]=3 < 5 → left=2, область [2..2]Шаг 3: mid=2, nums[2]=5 === 5 → return 2
Итого 3 проверки = log₂(8) ✓Сложность
Заголовок раздела «Сложность»Сравнение алгоритмов поиска при разных n:
| Алгоритм | n=8 | n=100 | n=10⁶ | n=10⁹ |
|---|---|---|---|---|
| Linear Search | 8 | 100 | 10⁶ | 10⁹ |
| Binary Search | 3 | 7 | 20 | 30 |
При миллиарде элементов linear search — миллиард операций, binary — всего 30.
Шпаргалка структур данных
Заголовок раздела «Шпаргалка структур данных»| Структура | Access | Search | Insert | Delete | Память |
|---|---|---|---|---|---|
| Массив | O(1) | O(n) | O(n) | O(n) | O(n) |
| Динамический массив | O(1) | O(n) | O(1) amort. | O(n) | O(n) |
| Связный список | O(n) | O(n) | O(1)* | O(1)* | O(n) |
| Стек / Очередь | O(n) | O(n) | O(1) | O(1) | O(n) |
| Hash Table (avg/worst) | — | O(1)/O(n) | O(1)/O(n) | O(1)/O(n) | O(n) |
| Binary Heap | O(1) top | O(n) | O(log n) | O(log n) | O(n) |
| BST (avg/worst) | O(log n)/O(n) | O(log n)/O(n) | O(log n)/O(n) | O(log n)/O(n) | O(n) |
| AVL / Red-Black | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| B-tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Trie | O(k) | O(k) | O(k) | O(k) | O(alphabet·n) |
| Skip List | — | O(log n) | O(log n) | O(log n) | O(n) |
| Segment Tree | — | O(log n) range | O(log n) | O(log n) | O(n) |
| Union-Find (DSU) | — | O(α(n)) | O(α(n)) | — | O(n) |
* при наличии указателя на узел; k — длина ключа в Trie; α(n) — обратная функция Аккермана, ≤ 4 на практике.
Шпаргалка сортировок
Заголовок раздела «Шпаргалка сортировок»| Алгоритм | Best | Average | Worst | Память | Stable |
|---|---|---|---|---|---|
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | да |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | да |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | нет |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | нет |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | да |
| Radix Sort | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | да |
Timsort (Array.sort) | O(n) | O(n log n) | O(n log n) | O(n) | да |
Шпаргалка графовых алгоритмов
Заголовок раздела «Шпаргалка графовых алгоритмов»| Алгоритм | Время | Память | Комментарий |
|---|---|---|---|
| BFS / DFS | O(V+E) | O(V) | Обход графа |
| Dijkstra (heap) | O((V+E) log V) | O(V) | Неотрицательные веса |
| Bellman-Ford | O(V·E) | O(V) | Отрицательные веса, циклы |
| Floyd-Warshall | O(V³) | O(V²) | All-pairs shortest paths |
| Kruskal (MST) | O(E log E) | O(V) | Сортировка рёбер + DSU |
| Prim (MST, heap) | O(E log V) | O(V) | Похож на Dijkstra |
| Tarjan / Kosaraju | O(V+E) | O(V) | SCC |
| Топосорт | O(V+E) | O(V) | Только для DAG |
Типичные ошибки и подводные камни
Заголовок раздела «Типичные ошибки и подводные камни»- Не упоминать Big-O на собесе — главная ошибка. Интервьюер не догадается, что вы понимаете сложность.
- Путать time и space — O(n) дополнительной памяти тоже стоимость, не забывайте про неё.
- Игнорировать worst-case — hash в среднем O(1), но при плохой хеш-функции / атаке вырождается в O(n).
- Переполнение в
mid = (left + right) / 2при больших значениях — используйтеmid = left + Math.floor((right - left) / 2). - Binary search без сортировки — даст неправильный результат, всегда проверяйте предусловия.
- Бесконечный цикл в binary search при некорректных обновлениях
left/right. - Стек рекурсии: O(log n) для merge sort, O(n) для худшего quicksort, O(n) для DFS на дереве-палочке.
Follow-up вопросы интервьюера
Заголовок раздела «Follow-up вопросы интервьюера»- Почему binary search требует отсортированный массив? Решение «идти влево/вправо» основано на сравнении
nums[mid]с target. Без сортировки логика ломается — остаётся только linear O(n). - Стоит ли сортировать перед поиском? Зависит от количества запросов k. Для одного — нет (sort O(n log n) > linear O(n)). Для k > log n — да (sort + k·O(log n) выгоднее).
- Lower bound / first occurrence в массиве с дубликатами. Модифицированный binary search: при
nums[mid] === targetсдвигаемright = mid - 1, продолжая искать левее. - Rotated sorted array (
[4,5,6,7,0,1,2]). Определяем, какая половина отсортирована (nums[left] vs nums[mid]), проверяем target в ней — O(log n). - Big-O вложенных циклов. Внешний i: 0..n, внутренний j: i..n →
n + (n-1) + ... = n(n+1)/2 = O(n²). Классический «треугольник». - Big-O рекурсии. Master Theorem или рекуррентное соотношение. Merge sort:
T(n) = 2T(n/2) + O(n) = O(n log n). Naive Fibonacci:T(n) = T(n-1) + T(n-2) = O(2ⁿ).
Чеклист на собес
Заголовок раздела «Чеклист на собес»- Назвал Big-O до написания кода.
- Указал и время, и память отдельно.
- Уточнил, worst или amortized сложность.
- Сравнил свой подход с brute-force по Big-O.
- Знаю константы:
log₂(10⁶)≈20, лимит ~10⁸ оп/сек. - Помню, что
Array.sort()без компаратора лексикографический:[10,2].sort() === [10, 2]. Всегда(a,b) => a - b.