这段代码中的增长函数和顺序是什么？

Question

我正在尝试理解这段代码的增长功能。

 for (int count=0; count < n; count++) {
   for (int count2=1; count2 < n; count2=count2*2) {
     System.out.println(count + ", " + count2);
   }
 }

Answer 1

外循环是线性的，因为每次都递增 1。内部循环是 log(n) 因为您的上限必须呈指数增长才能跟上 count2 变量的增长，因此整个嵌套迭代是 nlog(n) 。

Answer 2

当您刚开始了解增长和秩序时，解决这些问题的一个好方法是通过视觉思考。参考下图及说明：

假设 n = 8 并且打印是恒定时间操作。

先分别看看循环。

外循环相当简单：我们从计数 0 开始，每次将 count 递增 1，直到达到 n = 8。因此，我们必须递增 8/1 = 8 次才能完成循环。推广到n，循环会运行 n次。

内部循环稍微复杂一点：我们从计数 1 开始，然后通过将 2 乘以 count2 来递增，直到达到 n = 8。这样，count2 在每次迭代时增加 2 倍，其值可以由下式确定2^k 其中 k 是迭代次数。要计算达到 n = 8 需要多少次迭代，求解 2^k = 8 或 k = log2(8) = 3。推广到 n 循环将运行 for log2(n) 次。

结合这两个事实，对于外循环的每次迭代，内循环将是运行，因此总而言之，它将需要 n * log2(n) 到运行。因此，运行时间复杂度为O(nlog(n))

这段代码中的增长函数和顺序是什么？

What is the growth function and order in this code?

java

big-o

analysis