序列比对算法复杂度求解及opt算法时间复杂度分析

先贴出你提供的代码方便参考：

void opt(int i , int j ) { 
    if(i == m) opt = 2*( n - j); 
    else if(j == n) opt = 2*( m - i); 
    else{ 
        if(x[i] == x[j]) penalty = 0; 
        else penalty = 1; 
        opt = min(opt(i+1,j+1) + penalty, opt(i+1,j)+2, opt(i, j+1)+2); 
    } 
}

为什么这个算法的时间复杂度是O(3ⁿ)？ #

这个算法是无记忆化的暴力递归，低效的根源在于指数级分支+大量重复计算：

1. 分支数量：当i < m且j < n时，每次调用opt(i,j)都会触发3个全新的递归调用：
   • opt(i+1,j+1)（匹配/错配当前位置的字符）
   • opt(i+1,j)（跳过第一个序列的当前字符）
   • opt(i,j+1)（跳过第二个序列的当前字符）
2. 递归深度：假设两个序列长度相同（m = n，最坏情况），递归的最大深度是n（从i=0,j=0到i=n,j=n）。
3. 总计算量：递归树的每一层节点数都是前一层的3倍，总节点数是等比数列3⁰ + 3¹ + 3² + ... + 3ⁿ的和，当n足够大时，低次项可以忽略，总和近似为3ⁿ，因此时间复杂度为O(3ⁿ)。

举个直观的小例子：当n=2时，初始调用opt(0,0)会生成3个子调用；每个子调用若未触达边界，又会生成3个新调用，总调用次数是1+3+9=13，已经是3²的数倍。随着n增大，这个数量会以3的指数级爆炸增长。

另外，这个算法效率极低的核心原因是没有记忆化缓存：比如opt(1,1)可能会被多个不同的父调用重复计算，完全做了无用功。如果加上记忆化（比如用二维数组存储已计算的opt(i,j)结果），时间复杂度会直接降到O(mn)，这也是经典Needleman-Wunsch序列比对算法的优化思路。

内容的提问来源于stack exchange，提问作者nagi gee