像下面的函数，如何计算它的时间复杂度？我认为应该是 O(m*n)...
int uniquePaths(int m, int n) {
if (m < 1 || n < 1) return 0;
if (m == 1 && n == 1) return 1;
return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
}
最佳答案
您可以使用递归函数 T(m,n) = T(m-1, n) + T(m, n-1) 对时间复杂度进行建模，其中T(1,1)=1和T(m,n)=0每当min(m,n)<1 .
看起来像T(m,n)=(m+n choose m) 。看到这个说明(m+n choose n) = (m+n-1 choose m) + (m+n-1 choose m-1)由recurrence for the binomial coefficients ，以及T(m,n) = T(m-1, n) + T(m,n-1)是完全相同的重复。
因此T(m,n) = O((m+n)^n / n!) 。 (有many other bounds。)
关于algorithm - 如何计算DFS算法的时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36386237/