我认为big-O时间复杂性为4^(行+列(，其中行和列属于网格。
class Solution
{
public void someMethod(int[][] grid, boolean[][] used)
{
compute(grid, 0, 0, 0, used);
}
private void compute(int[][] grid, int i, int j, int count, boolean[][] used)
{
if(i<0 || j<0 || i>= grid.length || j>=grid[0].length || grid[i][j]==0 || used[i][j])
return;
if(grid[i][j] == 1000) // looking to find 1000 from starting position
{
return;
}
used[i][j] = true;
compute(grid, i+1, j, count+1, used); // Go down
compute(grid, i-1, j, count+1, used); // Go up
compute(grid, i, j+1, count+1, used); // Go right
compute(grid, i, j-1, count+1, used); // Go left
used[i][j] = false;
}
}
有人能解释一下时间的复杂性吗？此外，也有人可以为复杂的时间复杂性分析提供很好的有用资源/例子，比如2^n，n^n，n！etc
设n = columns和m = rows。为了简单起见，假设n == m。
Short：您的算法是O[ (2.6382)^(n^2) ]和Ω[ (1.3196)^(n^2) ]。
第一个是渐近上界，第二个是渐近下界。在任何情况下，对于某些c>1，与c^(n^2)一样快速增长的函数被称为双指数函数。它的增长速度比任何指数或阶乘都快。
请参阅下面的推导(尽管有些参数被缩短了(。关于特定问题的更好的界限可能是已知的，我没有研究它。这只是给出了如何解决这些问题的想法。
您想要计算2D网格(n，m(上从(0,0(开始的最大自回避路径的数量。还有一些额外的成本，比如实际的呼叫深度，但它们是多项式校正，而整个复杂性肯定是超指数的。
我将尝试在下面构建越来越好的复杂度上下限。
请注意，网格上的自回避路径最多可以具有n^2的长度(因为在许多步骤之后，所有used都为真(。因此，我们也可以忽略路径应该是最大的这一事实，因为如果我们也计算最大路径的每个非最大子路径，它最多将是多项式因子n^2的差。
在路径的每一步，我们可以走4个方向(4个compute调用(，因此相关路径的数量最多可以是4^(n^2)。然而，我们可以注意到，4步骤中至少有一个回到了我们已经到达的位置(或开始的位置(，因此不是自我回避的。因此，上界也是CCD_ 14。
更具创造性的是，我们可以意识到，从网格上的一个固定点开始的固定长度s的自回避路径的数量在所有方向上都是无限的，已知在具有生长常数µ的s中增长为指数多项式因子，称为连接常数。对于二维正方形晶格是不完全已知的，但它大致是µ = 2.6381...。对于无限网格，有限网格上这样的路径的数量当然更小，在s中路径的数量也肯定是单调的，所以问题的另一个上界是µ^(n^2 + O(log n))。
现在是下限。考虑案例n==2。在这个网格上，每个单元都可以通过至少2条不同的自回避路径从另一个单元到达。现在再次考虑较大的n，并将整个网格划分为2x2个子网格。在子网格来自的外部n/2xn/2网格上肯定存在至少一个长度为CCD_ 23的自回避路径。但是，正如刚才所说，在每个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)。其对于CCD_ 35到无穷大给出下限CCD_。
现在，可以尝试通过不将其粗粒化为2x2网格，而是将其重制为3x3网格来进行绑定。然后可以发现，在任何一对边界单元之间至少有9条路径，因此，使用与上述相同的参数，可以找到绑定的9^(n^2 / (3^2-1)) = (1.316...)^(n^2)。
可以对其他粗颗粒化重复这一点，我发现了4x4网格的最佳边界，假设任何一对边界单元之间的最小64自回避路径(实际上可能更高，没有枚举所有(为64^(n^2 / 15) = (1.3195...)^(n^2)。