递归 Levinshtein 算法的下界

Question

就时间复杂度而言，Levinshtein 距离算法的下界 (Omega) 是多少？算法描述如下：

// len_s and len_t are the number of characters in string s and t respectively
int LevenshteinDistance(string s, int len_s, string t, int len_t)
{
  /* base case: empty strings */
  if (len_s == 0) return len_t;
  if (len_t == 0) return len_s;

  /* test if last characters of the strings match */
  if (s[len_s-1] == t[len_t-1])
      cost = 0;
  else
      cost = 1;

  /* return minimum of delete char from s, delete char from t, and delete char from both */
  return minimum(LevenshteinDistance(s, len_s - 1, t, len_t    ) + 1,
                 LevenshteinDistance(s, len_s    , t, len_t - 1) + 1,
   `             LevenshteinDistance(s, len_s - 1, t, len_t - 1) + cost));
}

我知道这里已经回答了这个问题：Complexity of edit distance (Levenshtein distance) recursion top down implementation。但是我不明白 Omega(2^(max(m,n))) 是怎么推导出来的？我通过某种规则、示例或数学推导寻求推导。

Answer 1

前两次调用的递归深度低于 max(m, n)，因为它们每次都恰好减少了一个字符串的长度；对于三个调用，递归深度低于 min(m, n)，它们减少了两个字符串的长度（在最好的情况下）。这解释了 2 或 3 的幂。

递归 Levinshtein 算法的下界

Lower bound of recursive Levinshtein algorithm

algorithm

recursion