java - 以下代码的增长顺序

Question

以下代码片段的最坏情况运行时间随 N 的增长顺序是什么？ 

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++;

Answer 1

1. 外层循环一直运行到 i*i >= N，这意味着它总共运行了
   sqrt(N) 次。
2. 对于外循环的每次迭代，内循环运行直到 j*j >= 4*N，同样这意味着它运行 sqrt(4N) = 2sqrt(N) 次。
3. 对于中间循环的每次迭代，内部循环运行直到 k>=N*N，这意味着 N^2 次迭代。
4. 在恒定时间内增加总和。

将上面的内容相乘，因为你对 (2) 的每次迭代执行 (3)，对 (1) 的每次迭代执行 (2)，你得到 sqrt(N)*2sqrt(N)*N^ 2 = 2N^3，也就是 O(N^3)