计算具有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 ⁴),但正确的答案是:

答案是:N ⁷

对于给定的i值,最内循环的主体执行1 ² + 2 ² + 3 ² + ... +(i ²)² ~1/3 i ⁶次.总结i的所有值得到~1/21 N ⁷.

我想帮助理解这个答案以及在这种情况下计算复杂性的正确方法.

编辑:特别是,我不明白这句话:

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

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

Answer 1

编辑:

我将添加一些解释,以澄清您对问题中引用的疑惑.让我们考虑一个固定值,i并关注最里面的两个循环:

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

重复循环j次循环多少次？答案是i ^ 2次.在每个这些迭代时,第k循环迭代J(1)的2倍,这是每个外迭代不同的,因为j的增加值从1一直到I ^ 2.

当j = 1时,k循环迭代1 ^ 2次.当j = 2时,k循环迭代2 ^ 2次.当j = 3时,3 ^ 2次.在j的所有值上计算k循环的迭代总数,你有1 ^ 2 + 2 ^ 2 + 3 ^ 2 + ... +(i ^ 2)^ 2,因为j在1之间运行和我^ 2.希望这能说明您如何达到以下声明:

对于给定的i值,最内循环的主体执行1 ² + 2 ² + 3 ² + ... +(i ²)² ~1/3 i ⁶次.

迭代总数可以以总和形式表示.最里面的循环j^2对j的每个(变化的)值具有精确的迭代,中间循环i^2对于i的每个值具有迭代,并且最外面的循环具有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的大值,它可能会冻结你的浏览器,因为迭代次数增长得非常快).