大 O for 3 嵌套 for 循环？

Question

public int Loop(int[] array1) {
        int result = 0;
        for (int i = 0; i < array1.length; i++) {
            for (int j = 0; j < array1.length; j++) {
                for (int k = 1; k < array1.length; k = k * 2) {
                    result += j * j * array1[k] + array1[i] + array1[j];
                }
            }
        }
        return result;
    }

我想在这里找到计算算术运算次数的复杂度函数。我知道复杂度 class 是 O(n^3)，但我在计算步数时遇到了一些麻烦。

到目前为止我的推理是算术运算的次数是 8，那么复杂度函数是否只是 8n^3？

任何正确方向的指导将不胜感激，谢谢！

Answer 1

如果我们同意以下是一大步： result += j * j * array1[k] + array1[i] + array1[j] 然后我们称其为 incrementResult.

这里调用了多少次incrementResult？ (log n)

for (int k = 1; k < array1.length; k = k * 2) {
  // incrementResult 
}

让我们称之为 loop3。那么这里调用了多少次loop3呢？ (n)

for (int j = 0; j < array1.length; j++) {
  // loop 3
}

我们称其为 loop2。那么这里调用了loop2多少次呢？ (n)

for (int i = 0; i < array1.length; i++) {
  // loop 2
}

将所有这些相乘，你就会得到答案:)

Answer 2

第一个循环将运行 n 次，第二个循环将运行 n 次但是第三个循环将运行 log(n) 次（基数 2）。由于每次逆运算都是取对数，因此您将 k 乘以 2。相乘我们有 O(n^2 log(n))

Answer 3

这取决于循环。例如：

for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
        for (int k = 0; k < 10; k++) {
            sum += i * j * k;
        }
    }
}

复杂度为O(1)，因为迭代次数完全不依赖于输入。

或者这样：

for (int i = 0; i < n*n*n*n*n*n; i++) {
    sum += i;
}

是 O(n^6)，即使只有一个循环。

真正重要的是每个循环进行了多少次迭代。

在你的例子中，很容易看出最内层循环的每次迭代都是 O(1)。有多少次迭代？在达到 n 之前，您需要将数字加倍多少次？如果 x 是迭代次数，我们将在第一个 x 处退出循环，使得 k = 2^x > n。你能为 x 解决这个问题吗？

第二个循环的每次迭代都会这样做，所以第二个循环的成本是迭代次数（这次更容易计算）乘以内部循环的成本。

而第一个循环的每次迭代都会这样做，所以第一个循环的成本是迭代次数（也很容易计算）乘以第二个循环的成本。

总的来说，运行时间是 3 个数字的乘积。你能找到他们吗？

大 O for 3 嵌套 for 循环？

Big O for 3 nested for loops?

java

complexity-theory

big-o