algorithm - 您如何获得序列比对算法的复杂性？

Question

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

为什么这个算法的复杂度是 3^n ？

分析算法选择的时间复杂度。

标签： algorithm

Answer 1

您应该首先指定如何调用此函数。关于大O的分析，可以通过绘制递归树得到。您可以对小n样本执行此操作，您会注意到树的高度为n. 现在，您可以注意到对于函数的每个实例，您再次调用相同的函数 3 次，因此您有一个以指数方式扩展 3 倍的树。因此，您的复杂性是O(3^n).

奖励：类比斐波那契

检查斐波那契算法的基本（没有记忆）recusive 版本，您将看到类似的结构，除了每次执行 2 次调用这一事实，因此复杂度为O(2^n).