Я реализую алгоритм обратного отслеживания для решения головоломок Судоку, и мне необходимо провести эмпирический анализ алгоритма.Тем не менее, я испытываю трудности в понимании временной сложности этого алгоритма возврата для решения головоломки Судоку.Доска судоку - это сетка 9 на 9, поэтому каждое пустое пространство может принимать значения от 1 до 9, но сначала она проверяет строку, столбец, поле 3х3, чтобы убедиться в том, что это безопасно, и есть m пустых мест.Я перебираю сетку строка за строкой в поисках пустого места, а затем перебираю числа 1-9, проверяя, какое число безопасно разместить.Если номер безопасен, я помещаю его туда, затем снова вызываю мою функцию (повторение), чтобы проверить следующий пробел и так далее.Если это не приводит к решению, алгоритм возвращает назад, а затем помещает следующее число в это пространство и пытается снова.
Мне нужно будет создать сетки, которые будут наилучшей / худшей временной сложностью алгоритма обратного отслеживания.Поэтому, чтобы сделать это, мне нужно понять временную сложность реализованного алгоритма возврата.Если кто-то может помочь мне объяснить сложность этого времени и то, как рассчитывается лучший / худший случай для отслеживания судоку, или если кто-то может связать меня с соответствующими документами, которые могут быть полезны, я был бы очень признателен.
Заранее спасибо :)