Как рассчитать временную сложность этого алгоритма рекурсии

Question

Как рассчитать сложность времени следующей части кода? Пусть т близко к п. Я получил 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 в общий результат, поэтому количество листьев уникально. Пат (m, n). Поскольку uniquePaths (m, n) == «m + n-2 выбирает n-1», когда m и n похожи, время выполнения вашего алгоритма будет примерно равным центральному биномиальному коэффициенту «2n выбрать n», который находится в O (4^п).