如何計算此遞歸算法的時間複雜度

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）。