time-complexity - 递归代码的复杂度分析

Question

 function(int n)
 {
  if(n<=1)
  return;
  for(int i=1;i<=3;i++)
  function(n-1);
 }

现在要计算这个问题的复杂性，我们必须使用减法主定理。现在我推导出了结果为的递归关系T(n)=c+3T(n-1)。n>1但是如何使用减法主定理计算这个问题的复杂性，因为在主定理f(n)=O(n^d)中 d>0 .但是这里是c，它是一个常数项，而不是格式O(n^d)。那么如何解决这个问题呢？

Answer 1

减去和征服递归的大师定理适用于形式的递归

T(n) = aT(n-b) + f(n). iff f(n) in O(n^d) for some d >= 0

在这种特殊情况下，您有以下内容：

a = 3, b = 1, f(n) = c.

因为 c 是常数，所以让d = 0, f(n)in 。O(n^d) = O(1)

所以我们现在可以应用大师定理

因此T(n)在O(n^d * a^(n/b))自a > 1

现在插入我们的值，我们得到

T(n) in O(n^0 * 3^(n/1)) <=> O(3^n)

有用的来源：https ://www.eecis.udel.edu/~saunders/courses/320/10f/recurrence-relations.pdf