java - 寻找增长函数和大 O

Question

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

代码如下:

// 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)。如果有人可以就寻找增长函数或纠正我目前的工作提出任何建议，请告诉我。

Answer 1

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

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

我们将从评估外部 for 循环开始。变量 count 将被赋值多少次？这段逻辑只会执行一次，所以这里的答案是 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 )。