Big O нотация, временная и пространственная сложность, анализ алгоритмов
Сложность алгоритмов
Big O нотация
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) в среднем)
Выбирайте подходящие структуры данных: массивы для прямого доступа, списки для частых вставок/удалений
Учитывайте не только временную, но и пространственную сложность при работе с большими объемами данных