Как рассчитать временную сложность для алгоритма обратного прослеживания

Question

Подробная информация о вопросе и алгоритма

Учитывая сетку MxN, сколько путей могут там быть, чтобы достичь нижней правой ячейки из верхней левой ячейки? На любой сетке вы можете перемещаться в четырех направлениях. Единственное ограничение состоит в том, что нельзя посещать ячейку более одного раза.

Мы можем использовать возвраты алгоритма для решения этой проблемы, вот код (reference):

public class Robot { 
    private static int count = 0; 
    public static void main(String[] args) { 
     Robot robot = new Robot(); 
     int m = 5, n = 5; 
     boolean Visited[][] = new boolean[5][5]; 
     for(int i=0;i<m;i++){ 
      for(int j=0;j<n;j++) 
       Visited[i][j] = false; 
     } 
     robot.traverse(Visited, 0, 0, m, n); 
     System.out.println(count); 
    } 
    /** 
    * 
    * @param Visited array 
    * @param index i 
    * @param index j 
    * @param max Row m 
    * @param max column n 
    */ 
    private void traverse(boolean Visited[][], int i, int j, int m, int n){ 
     if(i==m-1&&j==n-1){ 
      count++; 
      return; 
     } 
     if(isSafe(i, j, m, n, Visited)){ 
      Visited[i][j]=true; 
      traverse(Visited, i, j+1, m, n); 
      traverse(Visited, i+1, j, m, n); 
      traverse(Visited, i-1, j, m, n); 
      traverse(Visited, i, j-1, m, n); 
      Visited[i][j] = false; 
     } 
    } 
    /** 
    * 
    * @param index i 
    * @param index j 
    * @param max Row m 
    * @param max Column n 
    * @param Visited array 
    * @return isSafe or not 
    */ 
    private boolean isSafe(int i, int j, int m, int n, boolean Visited[][]){ 
     if(i>=0&&j>=0&&i<m&&j<n&&!Visited[i][j]) 
      return true; 
     else 
      return false; 
    } 

} 

Что я знаю?

У меня есть некоторые сведения о вычислении временной сложности рекурсивного алгоритма с использованием метода подстановки и метода рекурсивного дерева (reference). И я могу рассчитать временную сложность некоторых более простых алгоритмов (например, Fibonacci Sequence).

Что я сделал, прежде чем размещать вопрос здесь?

Я проверил this, this, this и многие другие ссылки. Но я не могу объединить всю эту информацию и выяснить временную сложность этого вопроса.

Я попытался использовать метод повторяющегося дерева для вычисления временной сложности. Но путь может быть очень скручен, когда M & N велико, я не знаю, как развернуть дерево, потому что разрешено четыре направления.

После прочтения this, у меня есть общее представление о том, что, возможно, я могу думать в терминах сетей остались:

1. Шаг 1 - Есть MxN сетки должны быть выбраны из, так что есть возможности MXN.
2. Шаг 2 - Есть только сетки MxN-1, из которых можно выбрать. Итак, мы имеем (MxN) x (MxN-1)
3. И так далее, до неизвестного конца.

Тем не менее, я не могу полностью понять временную сложность этого алгоритма.

Что я хочу знать?

Для алгоритма обратного слежения, как это, как мы полностью понимаем его временную сложность?

Любые мысли приветствуются.

Answer 1

Проблема оценки сложности выполнения T может быть решена следующим образом. Пусть P=M*N - общее количество ячеек на входе. В каждом рекурсивном вызове количество ячеек разрешающей способности уменьшается на единицу, и всего 4 рекурсивных вызовов; вычислительная стоимость базового случая, в которых не оставило ни одного допускаемых клетки, является постоянной, что означает, что

T(0) = C 

имеет место, где C некоторое подходящее значение.Для произвольного P, получаем рекуррентное соотношение

T(P) = 4*P(T-1) 

и с помощью индукции, можно доказать, что

T(P) in O(4^P) 

держит. В общем, время работы ограничено по экспоненте в числе ячеек ввода, что, однако, не означает, что эта граница является плотной.