Levenshtein距离递归算法的时间复杂度递推式求解求助

正确递推式推导 #

标准Levenshtein距离的递归逻辑中，当两个字符串的当前字符不匹配时，会触发三个递归子问题：

• 删除第一个字符串的末尾字符，递归处理剩余部分
• 向第一个字符串末尾插入匹配字符，递归处理剩余部分
• 替换第一个字符串的末尾字符，递归处理剩余部分

输入规模与子问题规模 #

若定义输入规模N = m + n（m、n分别为两个字符串的长度），最坏场景下（两个字符串完全不匹配，每次递归都触发三个子问题），当m = n时，每个子问题的输入规模均为N-2（两个字符串各缩短1位，总长度减少2）。

非递归项的判定 #

每次递归调用中，除了触发子问题外，仅需执行常数时间操作：即比较当前末尾字符是否相等、返回最小值的简单判断，因此递推式中的非递归项是常数d，而非线性项dN。

最终，最坏情况下的递推式为：

T(N) = 3T(N-2) + d （d为常数）

复杂度计算与递推项区分 #

主定理应用结果 #

对上述递推式做变量替换（令k = N/2），可转化为线性递推：T(2k) = 3T(2(k-1)) + d，解得时间复杂度为Θ(3^(N/2))，等价于你推导的2^(N log₄3)（因log₄3 = (log₂3)/2，代入后可化简为同一结果）。

如何区分常数d与线性项dN #

核心看每次递归中，非递归操作的时间复杂度：

• 若仅需常数次操作（如字符比较、简单条件判断），则非递归项为常数d；
• 若需要遍历整个输入字符串（如逐字符预处理、统计），则非递归项为线性项dN。

Levenshtein递归每次仅处理当前末尾的单个字符，无遍历整个输入的操作，因此非递归项是常数。

内容的提问来源于stack exchange，提问作者Sunny Dao