如何计算回溯算法的时间复杂度

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). And I can calculate the time complexity of some easier algorithms(e.g. Fibonacci Sequence)。

在这里发布问题之前我做了什么？

我检查了 this, this, this 和许多其他链接。但是我无法将所有这些信息组合在一起并找出这道题的时间复杂度。

我尝试使用递归树方法来计算时间复杂度。但是当M&N很大的时候路径会很曲折，我不知道怎么展开这棵树，因为四个方向都是允许的。

看完this，我大概有了一个大概的想法，也许我可以考虑剩下的网格：

第 1 步 - 有 MxN 个网格可供选择，因此有 MxN 种可能性。
第 2 步 - 只有 MxN-1 个网格可供选择。所以我们有 (MxN)x(MxN-1)
以此类推，直到未知的结局。

不过，我还是不能完全理解这个算法的时间复杂度。

我想知道什么？

对于这样一个回溯算法，我们如何充分理解它的时间复杂度？

如有任何想法，我们将不胜感激。

Answer 1

估算运行时复杂度的问题T可以按如下方式解决。设 P=M*N 为输入中的单元格总数。每次递归调用，permittet cells减1，总共有4次递归调用；基本情况的计算成本是不变的，其中没有允许的单元格，这意味着

T(0) = C

成立，其中 C 是一些合适的值。对于任意P，我们得到递归关系

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

并使用归纳法，我们可以证明

T(P) in O(4^P)

成立。总的来说，运行时间在输入的单元格数量上呈指数增长，但这并不意味着这个界限很紧。

如何计算回溯算法的时间复杂度

How to calculate time complexity for a backtracking algorithm

complexity-theory

time-complexity

recursive-backtracking