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

使用嵌套循环和大 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)。因此，我们可以用基本上表示“执行我们关心的 θ(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² )您尝试计数的打印输出。