用3个循环计算算法的复杂度

本文介绍了用3个循环计算算法的复杂度的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 我试图解决以下问题： 以下代码片段的最坏情况运行时间的增长顺序是N的函数是什么？ int sum = 0;对于（int i = 1; i< = N; i ++），对于（int j = 1; j< = i * i; j ++） for（int k = 1 ; k< = j * j; k ++） sum ++; ，我发现复杂度为O（n ），但是正确的答案是：我想帮些忙来理解这个答案以及在这种情况下计算复杂度的正确方法。 EDIT：特别是，我不理解该语句： 1 + 2 + 3 + ... +（i ）〜 1/3 i 对我来说， + 2 + 3 + ... +（i ）〜i 解决方案编辑： 我将添加一些解释，以消除您对问题中引号的困惑。让我们考虑一个固定值 i 并关注最里面的两个循环： for（int j = 1; j< = i * i; j ++） for（int k = 1; k< = j * j; k ++） sum ++; j循环迭代了多少次？答案是i ^ 2次。在每个 迭代中，k循环都迭代j ^ 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。希望可以阐明您如何得出以下语句： 迭代总数可以以求和形式表示。对于每个（不同）的j值，最里面的循环都具有完全 j ^ 2 个迭代，中间的循环具有 i ^ 2 对每个i值进行迭代，并且最外面的循环具有 N 个迭代。更整洁地，确切的迭代次数是： 通过相乘，您会发现这是N中的7阶多项式，因此很明显为什么这是O（N ^ 7）。 如果您怀疑上面的答案是正确的，只需运行自己的代码并比较 sum 的值即可得到上面提供的公式： var sum = 0; var N = 10; 用于（var i = 1; i< = N; i ++）用于（var j = 1; j< = i * i; j ++） for（ var k = 1; k< = j * j; k ++） sum ++; 函数T（N）{返回（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的值较大，因为迭代次数会快速增长，它可能会冻结浏览器）。 I tried to solve the following exercise :What is the order of growth of the worst case running time of the following code fragmentas a function of 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++;and I found that the complexity is O(n), however the correct answer is :I would like some help to understand this answer and the correct way to calculate complexity in this case.EDIT : In particular, I don't understand this statement :1 + 2 + 3 + ... + (i) ~ 1/3 iBecause for me, + 2 + 3 + ... + (i) ~ i 解决方案 EDIT:I'll add a bit of explanation to clear up your confusion about the quote in your question. Let's consider a fixed value of i and focus on the innermost two loops:for (int j = 1; j <= i*i; j++) for (int k = 1; k <= j*j; k++) sum++;How many times is the j-loop iterated? The answer is i^2 times. On each of those iterations, the k-loop is iterated j^2 times, which is different for each outer iteration because the value of j increases from 1 all the way to i^2. When j = 1, the k-loop iterates 1^2 times. When j = 2, the k-loop iterates 2^2 times. When j=3, 3^2 times. Tallying up the total number of the iterations of the k-loop over all values of j, you have 1^2 + 2^2 + 3^2 + ... + (i^2)^2, since j runs between 1 and i^2. Hopefully that clarifies how you arrive at the following statement:The total number of iterations can be expressed in sum form. The innermost loop has exactly j^2 iterations for each (varying) value of j, the middle loop has i^2 iterations for each value of i, and the outermost loop has N iterations. More neatly, the exact number of iterations is:Multiplying through, you'll find this is a 7th order polynomial in N, so it is apparent why this is O(N^7).In case you doubt the answer above is correct, simply run your own code and compare the value of sum you get with the formula provided above: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));Here's a demo: http://jsfiddle.net/wby9deax/. No matter what value of N you put in the answer will be correct (note: be careful with large values for N, it will probably freeze up your browser, since the number of iterations grows very rapidly). 这篇关于用3个循环计算算法的复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！