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

Question

我刚刚开始解决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;
}

Answer 1

对于您的情况,递归关系是(let 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 = 2的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(ni)= t(0).so i = n

用等式(1)中的i值代替,得到2幂(n){t(0)}

所以我们的时间函数值将是2power(n),我们的程序复杂度等于bigoh(2power(n))