Сложность перебора с возвратом
Сложность перебора с возвратом — это оценка того, сколько вариантов алгоритм проверит и сколько времени займёт их обработка. Чем больше глубина поиска и число выборов на каждом шаге, тем быстрее растёт число проверяемых состояний.
Основная оценка
Если на каждом из \(k\) шагов есть не более \(b\) вариантов, то число последовательностей выбора не превышает \(b^k\). Поэтому временная сложность обычно оценивается как \(O(b^k)\). Число \(b\) называют branching factor — коэффициентом ветвления, а \(k\) — глубиной перебора.
Если варианты выбираются без повторений из \(n\) элементов, число порядков равно \(n!\). Например, при составлении перестановки алгоритм может рассматривать \(n\) вариантов на первом шаге, \(n-1\) на втором и так далее: \(n\cdot(n-1)\cdot\ldots\cdot1=n!\).
В полном переборе проверяются все допустимые варианты, поэтому оценка часто является точной или близкой к максимальной. В бэктрекинге неудачная ветвь может завершиться раньше, но в худшем случае алгоритм всё равно способен пройти почти всё дерево.
Нужно проверить все двузначные коды из цифр \(0\)–\(9\). На первой позиции 10 вариантов, на второй — 10 вариантов, всего \(10^2=100\). Если цифры нельзя повторять, вариантов будет \(10\cdot9=90\).
Оценка \(O(b^k)\) описывает рост числа операций при увеличении входных данных, а не точное время в секундах. Кроме того, отсечение ветвей перебора может сильно уменьшить фактическое число проверок, но не всегда меняет худшую асимптотическую оценку.
В алгоритме на каждом из 4 уровней есть по 3 выбора. Сколько листьев дерева поиска может быть в худшем случае?
Главное
- При \(b\) вариантах на каждом из \(k\) шагов число вариантов оценивают как \(b^k\).
- Для перестановок без повторений число вариантов равно \(n!\).
- Бэктрекинг и отсечение ветвей могут ускорить работу на практике, но худший случай часто остаётся экспоненциальным.