Какова временная сложность этой функции рекурсии

Question

Я столкнулся с следующим кодом, который используется для получения самой длинной общей подпоследовательности двух заданных строк. Он использует рекурсию, и временная сложность была задана как 2^n, но я не знаю, как этот результат был сгенерирован, может кто-нибудь помочь его проанализировать, спасибо.

/* A Naive recursive implementation of LCS problem */ 
#include<stdio.h> 
#include<stdlib.h> 

int max(int a, int b); 

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */ 
int lcs(char *X, char *Y, int m, int n) 
{ 
    if (m == 0 || n == 0) 
    return 0; 
    if (X[m-1] == Y[n-1]) 
    return 1 + lcs(X, Y, m-1, n-1); 
    else 
    return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)); 
} 

/* Utility function to get max of 2 integers */ 
int max(int a, int b) 
{ 
    return (a > b)? a : b; 
} 

/* Driver program to test above function */ 
int main() 
{ 
    char X[] = "AGGTAB"; 
    char Y[] = "GXTXAYB"; 

    int m = strlen(X); 
    int n = strlen(Y); 

    printf("Length of LCS is %d\n", lcs(X, Y, m, n)); 

    getchar(); 
    return 0; 
} 

Answer 1

В худшем случае, вызов lcs вызовет два вызова lcs:

return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)); 

Кроме того, если I=m+n то, что ребенок называет всегда удовлетворяют I_child <= I_parent - 1, Cf аргументы возможных рекурсивных вызовов:

return 1 + lcs(X, Y, m-1, n-1); 

и

return max(lcs(X, Y, m, n-1), lcs(X, Y, m-1, n)); 

так что если C(I) является сложностью lcs(X, Y, m, n), C(I) <= 2C(I - 1)+O(1) (отложите рекурсивный вызов, вы только выполнение сравнений, которые могут быть сделаны в постоянная время до тех пор, как целые числа ограничены, и они, на самом деле также скачки из-за утверждений, если это, но вы можете предположить, что это постоянное время)
так что мы имеем:

C(0) = O(1) 
C(I) <= 2C(I - 1) + O(1) <= O(1) + 2O(1) + 2^2O(1)+....+2^IO(1) 

следовательно

C(I) = O(2^I) 

или Условия m и n:

C(I) = O(2^max(m, n)) 

(Edit: эта оценка может быть улучшена)