这个代码段的增长顺序是什么？稍微解释一下

Question

int sum = 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++){
                sum++;
        }
    }
}

我知道这个代码段的增长顺序是N^3.But我需要对此进行适当的解释。

Answer 1

你可以一步一步分析循环，因为计数器是相互独立的：

外循环：执行了sqrt(n)次
中间循环：执行sqrt(4 * n) = 2 * sqrt(n)次。
内循环：执行了n^2次。
将结果相乘：sqrt(n) * 2 * sqrt(n) * n^2 = 2 * n^3.

因此遵循 O(n^3)。

Answer 2

I know the order of growth of this code segment is N^3

是的，你是对的。

总执行次数为sqrt(N) * sqrt(4 * N) * (N^2)即-

sqrt(N) * sqrt(4 * N) * (N^2)
=> 2 * sqrt(N) * sqrt(N) * (N^2)
=> 2 * N * (N^2)
=> 2 * (N^3)
=> O(N^3)

这个代码段的增长顺序是什么？稍微解释一下

what is the order of growth of this code segment?Explain little bit

java

algorithm

big-o