计算递归算法的时间复杂度

Question

我刚刚开始解决Topcoder算法问题，并用Java为SRM 466div 2 LotteryTticket问题编写了此算法。

由于我不擅长时间复杂性，所以如果有人能解释我如何一步一步地计算这个算法的时间复杂性。

public static String buy1(int price,int...b){
    int sum=0; String stat="IMPOSSIBLE";
    for(int i=0;i<b.length;i++)
        sum=sum+b[i];
    if(sum==price)
        return "POSSIBLE";
    if(b.length>1){
        stat=buy1(price,Arrays.copyOfRange(b,0,b.length-1));
        stat=buy1(price,Arrays.copyOfRange(b,1,b.length));
    }
    return stat;
}

Answer 1

对于您的案例，递归关系为（设b.length（）为bn）

                     ___________buy1(p,bn-1) (as (b,0,b.length-1) equivalent is bn-1 in number )
                    /
    buy1(p,bn) ____/
                   
                    ___________ buy1(p,bn-1)  (as (b,1,b.length) equivalent is bn-1 in number )

因此，对于n=n-1的两个子问题，我们的问题，因此我们的时间函数T（n）如下

   T(n)=2T(n-1)+c (For convenience lets eliminate c as it is very less compared to T(n) for this instance )
   T(n)=2[2(T(n-2))]
   T(n)=2{2[2(T(n-3))]} ===> 2poweri(T(n-i))  -------- equation(1)

当满足基本条件时，重复周期结束。假设T（0）=c（是基本条件），这意味着对于基本条件T（n-i）=T（0）。所以i=n

代入方程（1）中的i值，我们得到2次方（n）{t（0）}

因此，我们的时间函数值将是2power（n），并且我们的程序复杂性等于bigoh（2power（n））

Answer 2

您可以使用递归树方法和主方法来查找复杂性。

看看这个，了解更多关于如何解决这个问题的想法。

作为一个额外的练习，尝试使用这个来计算合并排序的复杂性。

Answer 3

有趣的问题。让我们正确地计算它；）因此，当条件（sum==price）永远不会出现时，我们将检查最坏的情况。

首先，让我们检查b.length=1时的完整性。那么您应该在循环中只使用一个"="操作：

for(int i=0;i<b.length;i++)

和2内部初始化：

int sum=0; String stat="IMPOSSIBLE";

下一步。让我们为N计算此任务。首先，您需要在第一个周期内进行N"="操作，在初始化内进行2次操作，在if.内进行2个操作

    stat=buy1(price,Arrays.copyOfRange(b,0,b.length-1));
    stat=buy1(price,Arrays.copyOfRange(b,1,b.length));

另一个操作是在递归步骤中进行的。因此，对于这种情况，我们可以使用递归公式，它等于：

f（n）=4+n+2*f（n-1），f（1）=3

该方程的解为：f（n）=-6+5*2^n-n

所以你们算法的复杂度是指数级的。O（2^n）我忽略了除"="之外的所有其他运算，因为它们不会改变渐近复杂性。