1

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

3 回答 3

5

对于您的情况，递归关系是 (let b.length() be 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(ni)=t(0) 用于基本条件.so i=n

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

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

于 2012-09-12T12:29:49.763 回答
2

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

查看此内容以获取有关如何解决此问题的更多想法。

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

于 2012-09-12T07:06:26.397 回答
2

有趣的问题。让我们正确计算它；）所以我们将检查条件（总和==价格）永远不会出现的最坏情况。

首先让我们检查 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^nn

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

于 2012-09-12T11:20:49.543 回答