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

我刚刚开始解决Topcoder算法问题，并在Java中为SRM 466 Div 2 LotteryTicket问题编写了此算法。计算递归算法的时间复杂度。

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

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

来源

2012-09-12 Aman Sharma

可以使用递归树的方法，掌握方法找到的复杂性。

查询this了解更多关于如何解决这个问题的想法。

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

来源

2012-09-12 07:06:26

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

首先让我们来看看complecity时将b.length = 1，那么你应该使用周期内仅只有一个 “=” 操作：

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

而且2内初始化：

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

下一页步。让我们计算一下N的任务。首先你需要在循环的第一个内部执行N“=”操作，在内部初始化的时候执行2个操作，在内部执行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^nn

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

来源

2012-09-12 11:20:49 Gloomcore

对于你的情况，复发关系（让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-1因此，我们的时间函数T N =两个子问题的问题（ 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（ni）= t（0）。 {t（0）}

所以我们的时间函数值是2power（n），我们的程序复杂度等于bigoh（2power（n））

来源

2012-09-12 12:29:49 Imposter

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

回答

相关问题