如何计算这种递归算法的时间复杂度

Question

如何计算以下代码的时间复杂度？假设m接近n。我得到的是f（n）=2*f（n-1）。所以时间复杂度是f（n）=O（2^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

下面的内容涉及到一些挥手，但我认为这基本上是正确的。

调用树中的每一个叶子将为总结果贡献1，因此叶子的数量是uniquePaths（m，n）。由于uniquePaths（m，n）=="m+n-2选择n-1"，当m和n相似时，算法的执行时间将大致为中心二项式系数"2n选择n"，即O（4^n）。