计算嵌套的复杂性循环

Question

我想计算的这种嵌套for循环的复杂性：

s = 0; 
for(i=1; i<=n; i*=2) 
    for(j=1; j<=i; j*=2) 
     s++; 

什么策略做我用它来找到这段代码的大O的复杂性？

Answer 1

外环游行通过1，2，4，8，... Ñ，这需要O（LG Ñ）步骤，因为你只能加倍一个O（LG Ñ）倍，直到击中n。

内循环也是如此。它只是上升到我，但在外部循环的最后一次迭代，我达到这又是ň它的最大价值，所以这也是O（LG ñ）。

把此一并给出了一个上界O（（LG Ñ）²），这是通常缩写的O（lg²Ñ）。

Answer 2

策略获得在N值不同的答案自己

插头插入公式，并进行了多少次的图表循环运行的最深处：

s = 0; 
for(i=1; i<=n; i*=2) 
    for(j=1; j<=i; j*=2) 
    s++; 

东西像这样：

n  num_times_inner_loop_part_runs 
1  1 
2  3 
3  3 
4  6 
5  6 
6  6 
7  6 
8  10 
9  10 
... 
15 10 
16 15 
... 
31 15 
32 21 

你可以得到这些数据点，像这样的程序：

int n = 9; //change this n 
int counter = 0; 
for(i=1; i<=n; i*=2){ 
    for(j=1; j<=i; j*=2){ 
    s++; 
    counter++; 
    } 
} 
cout << "counter is: " << counter << endl; 

绘制num_times_inner_loop_part在X/Y坐标平面上运行，您将看到一条曲线。

命名最接近的曲线。在这种情况下，它是X = (log(Y)^2)

如果您绘制数据和X = (log(Y)^2)，您会发现它们应该相互重叠。

因此，该功能的复杂性是O((log(n))^2)这是在这段代码的O(n)

Answer 3

时间分析的改进：

Answer 4

你的算法的时间复杂度可以正式被描绘成以下：

This document（上一张幻灯片）可能对您非常有用。