我该如何计算这个问题的复杂性？ [英] how do I calculate complexity of this question?

问题描述

在此代码段中，

In this code snippet,

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

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

now to calculate complexity of this question we have to use master theorem of subtraction.Now I deduced the recurrence relation which turns out to be T(n)=c+3T(n-1) for n>1.But how to calculate complexity of this question using master theorem of subtraction since in master theorem f(n)=O(n^d) where d>0.But here there it is c which is a constant term and not of the format O(n^d).So how to solve this?

推荐答案

这个问题相当于求解线性非齐次递推方程：

T（n）= h + 3T（n-1）; n> 1，

T（n）= h; n< = 1，其中h是操作成本< =。



1）在均匀递推方程中使用T（n）= a ^ n：T （n） - 3T（n-1）= 0.



a ^ n = 3a ^（n-1）=> a = 3



2）因此T（n）= b * 3 ^ n + c。



T（1）= h：3b + c = h

T（2）= 4h：9b + c = 4h

______________________________



=> b = h / 2，c = -h / 2



3）解是T（n）=（h / 2）*（3 ^ n - 1 ）



主要定理（用于减去和征服复发） [ ^ ]在这种情况下告诉我们？

注意a = 3，b = 1，d = 0.我们得到T（n）是在O（3 ^ n）。

This problem is equivalent to solving linear nonhomogeneous recurrence equation:
T(n) = h + 3T(n-1) ; n > 1,
T(n) = h ; n <= 1, where h is the cost of operation <=.

1) Use T(n) = a^n in homogeneous recurrence equation: T(n) - 3T(n-1) = 0.

a^n = 3a^(n-1) => a = 3

2) Thus T(n) = b*3^n + c.

T(1) = h: 3b + c = h
T(2) = 4h: 9b + c = 4h
______________________________

=> b = h/2, c = -h/2

3) The solution is T(n) = (h/2)*(3^n - 1)

What does Master theorem (for subtract and conquer recurrences)[^] tell us in this case?
Notice a = 3, b = 1, d = 0. We get T(n) is in O(3^n).

这篇关于我该如何计算这个问题的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！