Пусть n = columns и m = rows. Для простоты предположим n == m.
Short: Ваш алгоритм O[ (2.6382)^(n^2) ] и Ω[ (1.3196)^(n^2) ].
Первый - асимптотическая верхняя граница, а второй - асимптотическая нижняя граница. В любом случае функция, растущая так же быстро, как c^(n^2) для некоторого c>1, называется двукратно экспоненциальной. Он растет быстрее, чем любой экспоненциальный или факториальный.
См. Деривацию ниже (хотя некоторые аргументы сокращены). Лучшие оценки конкретной проблемы, вероятно, известны, я не исследовал ее. Это просто дает представление о том, как решить такие проблемы.
Вы хотите посчитать количество максимальных самостоятельных путей, начинающихся с (0,0) на двумерной сетке (n, m). Существуют некоторые дополнительные расходы, такие как фактическая глубина вызова, но они являются полиномиальными поправками, в то время как полная сложность, безусловно, суперэкспоненциальная.
Я постараюсь построить следующие лучшие и лучшие верхние и нижние оценки сложности.
Обратите внимание, что самонастраивающиеся пути в сетке могут иметь максимальную длину n^2 (потому что после этого много шагов все used имеют значение true). Поэтому мы также можем игнорировать тот факт, что пути должны быть максимальными, потому что если мы посчитаем каждый из немаксимальных подпутей также и максимальных, это будет не более чем полиномиальный множитель n^2 разница.
На каждом шаге пути мы можем пройти 4 направления (4 compute вызовов), поэтому количество соответствующих путей может быть не более 4^(n^2).
Однако мы можем заметить, что, по крайней мере, один из шагов 4 возвращается туда, где мы уже были (или к началу), и поэтому не является самообузданием. Таким образом, верхняя граница также равна 3^(n^2).
Будучи немного более креативным, мы можем понять, что число самодействующих путей фиксированной длины s, начинающихся в фиксированной точке на бесконечной во всех направлениях сетке, как известно, возрастает до полиномиальных факторов, экспоненциальных в s с постоянной роста µ, известной как соединительная постоянная . Для двумерной квадратной решетки это точно не известно, но это примерно µ = 2.6381....
Теперь это для бесконечной сетки, поэтому, конечно, число таких путей в конечной сетке меньше, и число путей также является монотонным в s, и поэтому еще одна верхняя граница для вашей задачи - µ^(n^2 + O(log n)).
Теперь для нижней границы. Рассмотрим случай n==2. В этой сетке каждая ячейка может быть достигнута друг от друга, по крайней мере, с двумя разными путями самообороны.
Теперь рассмотрим снова большее n и разделим всю сетку на 2x2 подрешетки.
На внешней сетке n / 2 x n / 2 есть, по крайней мере, один самозапирающийся путь длиной (n/2)^2, из которого выделены подсетки. Но также, как только что сказано, на каждой из n^2/4 подрешеток есть по крайней мере два эквивалентных пути на выбор. Следовательно, общее количество соответствующих путей составляет не менее f_0(n) = 2^(n^2 / 4), что составляет около (1.189...)^(n^2).
Теперь это мы тоже можем улучшить. Рассмотрим n=4 и разделите сетку на 2x2 подрешетки. Затем в каждой подсетке есть 2 возможных пути, а также как минимум 2 возможных пути в грубой сетке, что составляет, по меньшей мере, 2^5 = 32 путей. Если теперь n снова велико, и мы разделим на подсетки длиной 4, то с тем же аргументом, что и раньше, существует как минимум f_1(n) = 32^(n^2 / 16) = (1.255...)^(n^2) таких путей.
Повторяя эту крупнозернистую сетку на 2x2 сетки, мы находим для каждой r границу 2^((sum 4^x for x=0..r)/4^(r+1)*n^2).
который для r до бесконечности дает нижнюю границу 2^(n^2 / 3) = (1.2599...)^(n^2).
Теперь можно попытаться переделать эту границу с помощью крупнозернистой структуры не в сетки 2x2, а в сетки 3x3. Тогда можно обнаружить, что между любой парой граничных ячеек существует не менее 9 путей, и, используя те же аргументы, что и выше, можно найти границу 9^(n^2 / (3^2-1)) = (1.316...)^(n^2).
Можно повторить это для других крупнозернистых, и я нашел лучшую границу для 4x4 сеток с предполагаемым минимумом 64 самодостаточных путей между любой парой граничных ячеек (на самом деле может быть выше, не перечислите все) даю 64^(n^2 / 15) = (1.3195...)^(n^2).