java - 两个循环中的增长顺序

Question

以下代码的增长顺序是什么？

   int result = 0;
   for (int i = 1; i <= n; i *= 2)
      for (int j = 0; j <= i; j++)
         result++;

答案应该是 n，但我不知道如何弄清楚。
如何计算这些循环中的增长顺序？

我的假设是外循环运行 (log n + 1) 次。内循环依赖于外循环，因为它使用 i。但是这怎么等于n呢？

Answer 1

每次为给定的 i 执行内循环，它有 i+1迭代。

因为我有值 2^0, 2^1, 2^2, 2^3, 2^4, ...

内循环所有执行的总迭代次数为

2^0 + 1 + 2^1 + 1 + 2^2 + 1 + ... + 2^k + 1 其中 2^k <= n

那受约束

2^0 + 2^1 + ... + 2^k + logn

现在我们有 geometric series 的总和:

2^0 + 2^1 + ... + 2^k = 2^(k+1) - 1 <= 2n - 1 since 2^k <= n

因此，您会得到以下限制:

2n - 1 + logn 

这是 O(n) .