以下函数的时间复杂度是多少？

Question

我正在阅读有关竞争性编程的书，遇到了一个问题，我们必须计算n*n矩阵中的所有可能路径。现在的条件是：`

1. All cells must be visited for once (cells must not be unvisited or visited more than once)
2. Path should start from (1,1) and end at (n,n)
3. Possible moves are right, left, up, down from current cell
4. You cannot go out of the grid

现在这是我的问题代码：

typedef long long ll;
ll path_count(ll n,vector<vector<bool>>& done,ll r,ll c){
    ll count=0;
    done[r][c] = true;
    if(r==(n-1) && c==(n-1)){
        for(ll i=0;i<n;i++){
            for(ll j=0;j<n;j++) if(!done[i][j]) {
                done[r][c]=false;
                return 0;
            }
        }
        count++;
    }
    else {
        if((r+1)<n && !done[r+1][c]) count+=path_count(n,done,r+1,c);
        if((r-1)>=0 && !done[r-1][c]) count+=path_count(n,done,r-1,c);
        if((c+1)<n && !done[r][c+1]) count+=path_count(n,done,r,c+1);
        if((c-1)>=0 && !done[r][c-1]) count+=path_count(n,done,r,c-1);
    }
    done[r][c] = false;
    return count;
}

如果在此定义递归关系，则可能类似于：T（n）= 4T（n-1）+ n ²这种递归关系正确吗？我不这么认为，因为如果我们使用主定理，那么它将给我们结果为O（4 ⁿ * n ²），我不认为这可能是这样的订单。

之所以这样说，是因为当我将其用于7*7矩阵时，它需要大约110.09 seconds，而我不认为n=7 O（4 ⁿ * n ²）应该花费那么多时间。

如果我们为n=7计算它，则大约指令可以是4 ⁷ * 7 ⁷ = 802816〜10 ⁶。对于这样的指令量，它不需要花费太多时间。因此，在这里我得出结论，我的递归关系是错误的。

此代码生成的输出作为111712的7，与书的输出相同。所以代码是正确的。

那么正确的时间复杂度是多少？

Answer 1

否，复杂度不是O(4^n * n^2)。

请考虑符号中的4^n。这意味着，最大深度为n-在您的情况下为7，并且每个级别有4个选择。但这种情况并非如此。在第8层，您还有多个下一步选择。实际上，您一直在分支，直到找到深度为n^2的路径。

因此，非严格限制将给我们O(4^(n^2) * n^2)。但是，此界限远非严格，因为它假定您从每个递归调用中都有4个有效选择。事实并非如此。

我不确定它可以紧多少，但是第一次尝试会将其降至O(3^(n^2) * n^2)，因为您无法从原来的节点进入。这个界限仍然远非最佳。