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

Я хочу математически рассчитать рецидивную связь для проблем алгорит 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));
}

Кто-нибудь может объяснить, как управлять этим рекуррентным отношением?


recurrence algorithm
person dead programmer    schedule 08.03.2013    source источник
comment
В худшем случае, когда строки разные, при каждом вызове lcs() вы почти удваиваете объем работы (вы вызываете lcs() 2 раза). Это дает вам экспоненциальную сложность.   -  person Alexey Frunze    schedule 08.03.2013
comment
@AlexeyFrunze, можете ли вы дать рекуррентное отношение для этого.   -  person dead programmer    schedule 08.03.2013

Ответы (1)


arrow_upward
1
arrow_downward

Рекуррентное соотношение будет:

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)

Здесь, если самая длинная ветвь имеет длину k, мы получим верхний предел, если предположим, что все остальные ветви также имеют высоту k. Поскольку и T(0,k), и T(k,0) являются константами, мы имеем

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

Or 

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

если n и m равны.

person SidR    schedule 08.03.2013
comment
Можете ли вы сказать мне, что N & M есть? Являются ли они левой / правой ветвями дерева? также откуда берутся X и Y? - person Auston; 22.05.2016
comment
@Auston Пожалуйста, проверьте функцию int lcs (...), предоставленные в вопросе для вашего ответа. - person SidR; 27.05.2016