algorithm - 如何计算DFS算法的时间复杂度？

Question

像下面这个函数，它的时间复杂度怎么计算？我认为应该是 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);
}

Answer 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 。)