java - 给定代码片段的大 O 表示法

Question

我正在寻找有关大 O 表示法的帮助。目标是给出给定代码片段的增长顺序。

int sum = 0
for (int k = n; k > 0; k/=2 )
  for (int i = 0; i < k; i++)
    sum++;

对于这个代码片段，我得到了 (N logN)。第一个 for 循环是 logN，第二个 for 循环是 N。

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

我在这方面遇到了一些麻烦。第一个 for 循环是 logN，但是第二个 for 循环是我陷入困境的地方。第二个 for 循环依赖于第一个 for 循环。我不知道如何用大 N 表示法来表示。

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

第一个 for 循环是 logN。第二个 for 循环是 N。所以这是 (N)？

我正在努力解决这个问题，希望得到一些帮助。谢谢

Answer 1

1. 您对第一个代码片段的判断是正确的:O(n*log n)。

2. 在第二个代码片段中，j 循环到 i，最高可达 n - 1，因此j for 循环本身的复杂度为 O(n)。但让我们看看会发生什么。

   • n = 16
   • i = 1 内循环运行 1 次。
   • i = 2 内循环运行 2 次。
   • i = 4 内循环运行 4 次。

   • i = 8 内循环运行 8 次。

   • n = 17

   • i = 1 内循环运行 1 次。
   • i = 2 内循环运行 2 次。
   • i = 4 内循环运行 4 次。
   • i = 8 内循环运行 8 次。
   • i = 16 内循环运行 16 次。

循环次数为

1 + 2 + 4 + ... + 2^x = 2^(x+1) - 1

其中 x 是 n 之前的 2 的幂。这个 2^(x+1) 可能高达 2n，因此整体复杂度为 O(n)，去掉常数“2”。

第三个代码片段与第二个代码片段类似；只是 j 每次都会一直到 n。这里的复杂度是O(n*log n)。