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

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

对于你的情况，递归关系是(令 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(be base condition) 这意味着 t(n-i)=t(0) for base condition .so i=n

将 i 值代入等式 (1) 中，我们得到 2power(n){t(0)}

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