java: 这个 do-while 代码片段的大哦顺序？加上严格的上限

Question

我知道这很容易，但我的教科书没有讨论带有 do-while 循环的 Big-Oh 顺序，我的任何其他算法源也没有。

此问题指出以下代码片段是在变量 "n" 上参数化的，并且还需要严格的上限。

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);

任何人都可以帮我解决这个问题并根据 do-while 循环解释 Big-Oh 顺序吗？它们与 for 循环一样吗？

Answer 1

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

"When in doubt, work from the inside out!"

这是您发布的代码：

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，无论是在循环之外还是在内部循环结束时）。因此，我们可以用基本上说 "do Θ(n) operations that we care about," 的内容替换该内部循环，如下所示：

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

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

java: 这个 do-while 代码片段的大哦顺序？加上严格的上限

java: Big-Oh order of this do-while code fragment? Plus a tight upper bound

java

big-o

upperbound