Big O нотация используется для описания асимптотической сложности алгоритма — как время выполнения или потребление памяти растёт с увеличением размера входных данных.
O(1) - константная сложность: время выполнения не зависит от размера входных данныхO(log n) - логарифмическая сложность: время растёт логарифмически (например, бинарный поиск)O(n) - линейная сложность: время растёт пропорционально размеру входных данныхO(n log n) - линейно-логарифмическая сложность (например, сортировка слиянием)O(n²) - квадратичная сложность: время растёт квадратично (например, пузырьковая сортировка)O(2ⁿ) - экспоненциальная сложность: время растёт экспоненциально
# Временная и пространственная сложностьВременная сложность описывает, сколько времени требуется алгоритму для выполнения.
Пространственная сложность описывает, сколько памяти требуется алгоритму для выполнения.
In-place сортировка (пузырьковая) — O(1) дополнительной памяти
Сортировка слиянием — O(n) дополнительной памяти для временного массива
Рекурсивный DFS — O(h) памяти для стека вызовов (где h — высота дерева)
При анализе алгоритмов важно учитывать:
Лучший случай (best case)
Средний случай (average case)
Худший случай (worst case)
Часто в Big O нотации указывается худший случай, так как он гарантирует верхнюю границу производительности.
# Практические рекомендации
Для больших данных избегайте алгоритмов с квадратичной и экспоненциальной сложностью
Используйте хэш-таблицы для быстрого поиска (O(1) в среднем)
Выбирайте подходящие структуры данных: массивы для прямого доступа, списки для частых вставок/удалений
Учитывайте не только временную, но и пространственную сложность при работе с большими объемами данных