1

对于以下每个代码片段，我需要说明增长函数以及顺序。我相当确定我已经正确确定了订单，但我正在努力了解如何从我提供的内容中推导出带有常量和所有内容的整个函数。

以下是代码片段：

// CODE #1
for (int count=0; count<n; count++)
{
    for (int count2=0; count2<n; count2=count2+2)
    {
        System.out.println(count + ", " + count2);
     }
}

// CODE #2
for (int count=0; count<n; count++)
{
    for (int count2=1; count2<n; count2=count2*2)
     {
         System.out.println(count + ", " + count2);
    }     
}

// CODE #3
for (int count = 0; count < n; count++) {
    printsum(count); }

// Here’s the method:

public void printsum(int count) {
    int sum = 0;
    for (int i=1; i<count; i++) {
        sum += i; 
    }
    System.out.println(sum + ": " + sum); 
    }

// CODE #4
for (int count = 0; count < n; count++) 
{
    printsum(count); 
}

// Here’s the method:

public void printsum(int count) { 
    int sum = 0;
    sum = count * (count + 1)/2; 
    System.out.println(“sum : " + sum);
}

我认为顺序是O(n^2), O(nlogn (base 2)),O(n^2)和O(n^3)。如果有人可以就找到增长函数或纠正我到目前为止的工作提供任何建议，请告诉我。

4

1 回答 1

4

构建增长率函数只是找出每个特定代码相对于 (n) 评估的次数。您将需要合并分配或初始化变量的次数以及循环检查它们是否已完成运行的次数。

我可以帮助代码 #1，剩下的留给你。

我们将从评估外部 for 循环开始。变量计数要分配多少次？这部分逻辑只会执行一次，所以这里的答案是 1。循环将执行多少次评估计数（小于）n？这部分代码总共将被评估 n+1 次，其中 n 次是循环实际运行的次数，另外一次是停止循环处理的评估。最后在外层for循环中，count变量会增加多少次（count++）？这将总共发生 n 次。

到目前为止，我们有什么？

到目前为止，我们的外部 for 循环给了我们一个函数： 

GRF = 1 + n+1 + n

现在开始我们的内部 for 循环。整个内部for循环会执行多少次？内部 for 循环将总共执行 n 次。这意味着我们需要将所有内部 for 循环进程乘以 n。我们的 GRF 最终会看起来像这样： 

GRF = 1 + n+1 + n + n(processes of the inner for loop)

暂时忽略 n 的乘法，我们将继续评估内部 for 循环，就像我们从上面执行外部 for 循环一样。变量count2的初始化会发生多少次？这将发生一次。代码 count2（小于）n 将被评估多少次？这部分有点棘手，因为您需要查看 count2 变量的递增率。在每次执行循环期间，它都会增加 2 的值。这意味着该变量的增长速度将增加一倍，而循环的计算次数将仅为该变量仅递增 1 时的一半。所以我们有 (n+1)/2。请记住，+1 说明了导致循环失败的评估，这里循环只会被评估一半的次数。现在，对于内部循环声明的最后一部分。count2 变量将增加多少次？这将发生 n/2 次。System.out.println() 将在内部 for 循环中执行多少次？这将发生与 count2 变量递增相同的次数，因此它将发生 n/2 次。

现在我们需要将所有这些评估插入上面 GRF 的内部 for 循环部分。我们最终会得到这样的结果： 

GRF = 1 + n+1 + n + n( 1 + (n+1)/2 + n/2 + n/2)

让我们做一个小代数

1 + n+1 + n + n( 1 + n/2 + 1/2 + n/2 + n/2)
1 + n+1 + n + n + (n^2)/2 + n/2 + (n^2)/2 + (n^2)/2
3(n^2/2) + 7n/2 + 2

我们去吧。增长率函数。为了得到 O(·)，我们只需保留最大项并去掉所有常数和因子，因此我们最终得到 O(n^2)。

于 2013-10-02T00:16:49.520 回答