Можете ли вы перечислить основные категории сложности алгоритмов и их критерии?

Основные категории сложности алгоритмов описывают, как время выполнения или использование памяти растут с увеличением размера входных данных (n). Вот основные классы:

• O(1) — константная сложность: время не зависит от размера данных.
• O(log n) — логарифмическая: время растёт пропорционально логарифму от n (например, бинарный поиск).
• O(n) — линейная: время пропорционально размеру входа.
• O(n log n) — линейно-логарифмическая: часто встречается в эффективных алгоритмах сортировки (например, быстрая сортировка).
• O(n²) — квадратичная: время растёт пропорционально квадрату размера входа (например, сортировка пузырьком).
• O(2^n) — экспоненциальная: время удваивается с каждым увеличением n (например, перебор всех подмножеств).
• O(n!) — факториальная: очень быстро растущая сложность (например, перебор всех перестановок).

Критерии оценки:

• Как меняется время/память при увеличении входных данных.
• Наихудший, средний и лучший случаи.

Понимание этих категорий помогает выбирать эффективные алгоритмы для задач.