Математическое рекуррентное отношение для вычисления сложности самой длинной общей подпоследовательности

Question

Я хочу математически вычислить рекуррентное отношение для задачи алгоритма LCS. Моя цель - применить теорему Мастера для вычисления сложности O (2^n).

/* 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)); 
} 

Любой может объяснить, как управлять этим возвратным отношением?

Answer 1

Рецидив соотношение будет:

T(n,m) = T(n-1,m-1)+O(1), if (X[m-1] = Y[n-1]) 
     or 
     T(n-1,m)+T(n,m-1)+O(1), otherwise 

Мы должны рассмотреть наихудший сценарий, который был бы:

T(n,m) = T(n-1,m)+T(n,m-1)+O(1) 

повсюду. Что бы сводиться к:

T(n,m) <= 2^(n-1) T(0,m) + ... , if m<n (longest branch of height n) 
     or 
     2^(m-1) T(n,0) + ... , if n<m (longest branch of height m) 

Здесь, если длинная ветвь длины к, мы получаем верхний предел, если взять на себя все другие ветви высоты к а. Так как оба T (0, к) и Т (К, 0) являются постоянными, мы имеем

T(n,m) = O(2^(max(n,m))) 

Or

T(n,m) = O(2^n) 

, если п и т равны.