循环的三倍增长顺序

Question

我正在练习算法的复杂性，我在网上找到了这个代码，但我无法弄清楚它的增长顺序。有任何想法吗？

int counter= 0; 
    for (int i = 0; i*i < N; i++) 
    for (int j = 0; j*j < 4*N; j++) 
    for (int k = 0; k < N*N; k++) 
    counter++; 

Answer 1

在一个时间把它一个步骤（或在这种情况下，循环）：

1. 第一环路增量i只要它的平方比N较低，所以这必须O(sqrt N)，因为int(sqrt(N))或int(sqrt(N)) - 1是平方值小于N的最大整数值;

2. 对于第二个循环也是如此。我们可以忽略4，因为它是一个常数，在处理大哦符号时我们不关心这些。所以前两个循环一起是O(sqrt N)*O(sqrt N) = O(sqrt(N)^2) = O(N)。由于循环是嵌套的，因此可以乘以复杂度，所以第二个循环将完全执行第一个循环的每个迭代;

3. 第三个循环显然是O(N^2)，因为k上升到了N的平方。

所以整个事情必须是O(N) * O(N^2) = O(N^3)。通常可以通过计算第一个循环的复杂性，然后第二个，然后是前两个等来解决这样的问题。

Answer 2

的Sqrt NX 2的Sqrt nxn的^ 2

其中给出：

，O n^3

说明：

对于第一环路，平方根二者的侧面方程式

i^2 = n

对于第二个循环，平方根的等式两边

J（1）2 = 4N^2

第三环是直线前进。