Как рассчитать сложность времени для алгоритма возврата

Question

Подробности вопроса и алгоритм

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

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

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;
    }

}

Что я знаю?

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

Что я сделал, прежде чем опубликовать вопрос здесь?

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

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

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

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)

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