三重 for 循环的增长顺序

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

平方 n x 2 平方 n x n ^ 2

给出：

On^3

解释：

对于第一个循环，等式两边都开平方

i^2 = n

对于第二个循环，等式两边都开平方

j^2 = 4n^2

第三个循环很简单。

Answer 2

一步一步（在本例中为循环）：

第一个循环递增 i 只要它的平方小于 N，所以这必须是 O(sqrt N)，因为 int(sqrt(N)) 或 int(sqrt(N)) - 1是平方小于N的最大整数值；
第二个循环也是如此。我们可以忽略 4 因为它是一个常量，我们在处理大 O 符号时不关心这些。所以前两个循环加起来就是O(sqrt N)*O(sqrt N) = O(sqrt(N)^2) = O(N)。您可以增加复杂性，因为循环是嵌套的，因此第二个循环将完全执行第一个循环的每个迭代；
第三个循环显然是O(N^2)，因为k往上就是N的平方。

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

Order of growth of triple for loop