Easybig-o
Что такое Big O notation и почему важно?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
Big O — асимптотическая оценка сложности алгоритма по мере роста входа n. Описывает верхнюю границу growth rate, игнорирует константы и младшие члены.
Основные классы (по возрастанию):
- O(1) — константная (хеш-таблица lookup);
- O(log n) — логарифмическая (бинарный поиск);
- O(n) — линейная (проход по массиву);
- O(n log n) — сортировки (merge, heap, quicksort в среднем);
- O(n²) — квадратичная (nested loops, bubble sort);
- O(2ⁿ) — экспоненциальная (наивный fibonacci, subsets);
- O(n!) — факториальная (permutations).
Амортизированная сложность — средняя на операцию (push_back в vector — O(1) amortized, несмотря на редкие O(n) reallocation). Best/Worst/Average: для quicksort O(n log n) average, O(n²) worst. Вложенные циклы по двум разным размерам — O(n·m).
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.