for循环 – 三个相互依赖的嵌套for循环的渐近分析
发布时间：2020-12-13 20:46:06 所属栏目：百科 来源：网络整理
导读：我要分析的代码片段如下： int sum = 0;for (int i = 0; i n; i++) for (int j = 0; j i * i; j++) for (int k = 0; k j; k++) sum++; 我知道第一个循环是O(n),但这就是我所知道的.我认为第二个循环可能是O(n ^ 2),但我想的越多,它的意义就越小.任何指导都将
|
我要分析的代码片段如下：
int sum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < i * i; j++)
for (int k = 0; k < j; k++)
sum++;
我知道第一个循环是O(n),但这就是我所知道的.我认为第二个循环可能是O(n ^ 2),但我想的越多,它的意义就越小.任何指导都将非常感谢.
第一个循环执行n次.每一次,我的价值都在增长.对于每个这样的i,第二个循环执行i * i次.这意味着第二个循环执行1 * 1 2 * 2 3 * 3 … n * n次.
这是平方和,其公式为well-known.因此,我们有第二个循环执行(n(1 n)(1 2 n))/ 6次. 因此,我们知道总共将有(n(1 n)(1 2 n))/ 6个j的值,并且对于这些中的每一个,第三个循环将执行1 2 … j = j(j 1 )/2次.实际上计算第三个循环总共执行多少次将是非常困难的.幸运的是,你真正需要的只是函数顺序的最小上限. 您知道,对于j的每个(n(1 n)(1 2 n))/ 6值,第三个循环将执行少于n(n 1)/ 2次.因此,可以说操作和将执行小于[(n(1 n)(1 2 n))/ 6] * [n(n 1)/ 2]次.经过一些快速的心算,这相当于最大度为5的多项式,因此你的程序是O(n ^ 5). （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |