计算具有 3 个循环的算法的复杂性

Question

我试图解决以下练习：

以下代码片段的最坏情况运行时间的增长顺序是什么作为 N?

的函数

int sum = 0;
for (int i = 1; i <= N; i++)
    for (int j = 1; j <= i*i; j++)
        for (int k = 1; k <= j*j; k++)
            sum++;

我发现复杂度是 O(n⁴)，但是正确答案是：

The answer is : N⁷

For a given value of i, the body of the innermost loop is executed 1² + 2² + 3² + ... + (i²)² ~ 1/3 i⁶ times. Summing up over all values of i yields ~ 1/21 N⁷.

我需要一些帮助来理解这个答案以及在这种情况下计算复杂度的正确方法。

编辑：特别是，我不明白这个说法：

1² + 2² + 3² + ... + (i ²)² ~ 1/3 i⁶

因为对我来说，² + 2² + 3² + ... + (i²)² ~ i⁴

Answer 1

int sum = 0;
for (int i = 1; i <= N; i++)            -- O(N^1)
    for (int j = 1; j <= i*i; j++)      -- O(N^2)
        for (int k = 1; k <= j*j; k++)  -- O(N^4)
            sum++;

因为它们是嵌套的（并且因为它们都是线性的）你得到 O(N¹ × N² × N ⁴) = O(N¹⁺²⁺⁴) = O(N⁷)

EDIT : In particular, I don't understand this statement :

1² + 2² + 3² + ... + (i²)² ~ 1/3 i⁶

请记住，您可能有 N 个术语隐藏在“…”部分。

Answer 2

编辑：

我将添加一些解释来消除您对问题中引用的困惑。让我们考虑一个固定值 i 并关注最里面的两个循环：

for (int j = 1; j <= i*i; j++)
    for (int k = 1; k <= j*j; k++)
        sum++;

j-loop迭代了多少次？答案是 i^2 次。在每个 those 迭代中，k 循环被迭代 j^2 次，每次外部迭代都是不同的，因为 j 的值从 1 一直增加到 i^2。

当 j = 1 时，k 循环迭代 1^2 次。当 j = 2 时，k 循环迭代 2^2 次。当j=3时，3^2次。计算 k 循环在所有 j 值上的迭代总数，您有 1^2 + 2^2 + 3^2 + ... + (i^2)^2，因为 j 运行s 在 1 和 i^2 之间。希望这能阐明您是如何得出以下陈述的：

For a given value of i, the body of the innermost loop is executed 1² + 2² + 3² + ... + (i²)² ~ 1/3 i⁶ times.

总的迭代次数可以用求和的形式表示。对于 j 的每个（可变）值，最内层循环恰好有 j^2 次迭代，对于 i 的每个值，中间循环有 i^2 次迭代，最外层循环有 N 次迭代。更巧妙的是，确切的迭代次数是：

乘以，你会发现这是N的7阶多项式，所以很明显为什么这是O(N^7)。

如果您怀疑上面的答案是否正确，只需运行您自己的代码并将您得到的 sum 的值与上面提供的公式进行比较：

var sum = 0;
var N = 10;

for (var i = 1; i <= N; i++)
    for (var j = 1; j <= i*i; j++)
        for (var k = 1; k <= j*j; k++)
            sum++;

function T(N) { return (1/420)*N*(1+N)*(1+2*N)*(8+11*N+21*N*N+20*N*N*N+10*N*N*N*N); }

console.log(sum===T(N));

这是一个演示：http://jsfiddle.net/wby9deax/。无论你在答案中输入的 N 值是多少都是正确的（注意：小心 N 的大值，它可能会冻结你的浏览器，因为迭代次数增长非常快）。

Answer 3

因为将会 N^1 循环 - 首先是 N^2 循环 - 第二个 N^4 循环 - 第三个 for 和 N^1 * N^2 * N^4 = N^7

Answer 4

我认为用 N 个值替换变量 (i、j 和 k) 是个好主意。

for (int i = 1; i <= N; i++) //<- i = N
    for (int j = 1; j <= i*i; j++) //<- i*i = N*N
        for (int k = 1; k <= j*j; k++) //<- j*j = (i*i)*(i*i) =  N*N*N*N

在第一个循环中，迭代次数为N，这是简单的部分。在第二个循环中，迭代次数将为 N*N。第三个 - N*N*N*N.

所以最后，迭代次数将是 N（第一次循环），次 N*N（第二次），次 N*N*N*N（第三次），所以 N*(N*N)*(N*N*N*N) = N^7

计算具有 3 个循环的算法的复杂性

Calculating the complexity of an algorithm with 3 loops

algorithm

complexity-theory

time-complexity