java：Big-Oh这个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); 

任何人都可以帮我解释Big-Oh命令的do-while循环吗？它们和循环一样吗？

Answer 1

一个很好的格言与嵌套循环和大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）次，因为我计数0,1,2，...，直到n。最终结果是这个循环运行了Θ（n）次，并且因为我们在每次迭代时都会执行Θ（n）操作，所以最终的效果是这样做的打印输出结果是Θ（n ）你正在努力数数。