算法复杂-嵌套for循环

for(j=n; j>1; j/=2) 
    ++p; 
for(k=1; k<p; k*=2) 
    ++q;

在第一代码示例，p可变属于第一回路。所以，即使它们没有嵌套循环，也会第二个返回日志（n）呢？我的意思是，O（loglog（n））？算法复杂-嵌套for循环

for(i=n; i>0; i--){ 
    for(j=1; j<n; j*=2){ 
    for(k=0; k<j; k++){ 
     //statements-O(1) 
    } 
    } 
}

而且这些中的一个，它们嵌套但ķ变量属于第二循环。那么，它应该与第一个类似吗？类似于O（n^2.log（n））或O（n.log^2（n））？

2017-04-06 Can Dirik

[如何找到时间算法的复杂度（http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm） –

算法：第一个循环取log（n）时间。第二个循环取log（log（n））时间。所以你有log（n）+ log（log（n））。但首先循环更重要。所以它是O（log（n））。算法：首先看看当你只分析两个外部for循环（表示n log（n））时你有什么运行时间。但不幸的是，这里出现了循环内部的三分之一，这使得它更加复杂。

第三个循环计数从0到2^m，其中m = log（n）。所以你必须从0到2^m的总和为log（n）-1，这是n-1。所以n-1是两个内部for循环的运行时间。现在，您必须将其乘以外循环的线性运行时间。所以它是（n-1）n是n 2 -n。所以你有三个循环的O（n²）。

2017-04-06 13:05:48 gartenkralle

感谢可能的复制您。现在我明白了第一个问题的返回值和运行时差异。 –

回答