0

I know this is easy but my textbook doesn't talk about Big-Oh order with do-while loops, and neither do any of my other algorithm sources.

This problem states that the following code fragment is parameterized on the variable "n", and that a tight upper bound is also required.

int i=0, j=0;

do {

    do {

          System.out.println("...looping...");  //growth should be measured in calls to println. 

          j=j+5;

       } while (j < n);

    i++;

    j = 0;

} while (i < n);

Can anyone help me with this and explain Big-Oh order in terms of do-while loops? Are they just the same as for loops?

4

1 回答 1

2

使用嵌套循环和大 O 的一个很好的格言是

“当有疑问时，由内而外地工作！”

这是您发布的代码：

int i=0, j=0;
do {
    do {
          Do something
          j=j+5;
    } while (j < n);
    i++;
    j = 0;
} while (i < n);

让我们看看那个内循环。它大约运行 n / 5 次，因为 j 从 0 开始，每一步增长 5。（我们还看到，在循环开始之前，j 总是重置为 0，无论是在循环之外还是在内部循环结束时）。因此，我们可以用基本上说“做我们关心的 Θ(n) 操作”的东西来替换那个内部循环，如下所示：

int i=0;
do {
    do Θ(n) operations that we care about;
    i++;
} while (i < n);

现在我们只需要看看它做了多少工作。请注意，这将循环 Θ(n) 次，因为 i 计数 0、1、2、...，直到 n。最终效果是这个循环运行了 Θ(n) 次，并且由于我们在每次迭代中都执行了我们关心的 Θ(n) 操作，因此最终效果是这会执行 Θ(n 2 ) 的打印输出重新数数。

于 2017-01-16T22:36:07.113 回答