以下代码片段的最坏情况运行时间随 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++;
最佳答案
- 外层循环一直运行到
i*i >= N，这意味着它总共运行了
sqrt(N)次。 - 对于外循环的每次迭代，内循环运行直到
j*j >= 4*N，同样这意味着它运行sqrt(4N) = 2sqrt(N)次。 - 对于中间循环的每次迭代，内部循环运行直到
k>=N*N，这意味着N^2次迭代。 - 在恒定时间内增加总和。
将上面的内容相乘，因为你对 (2) 的每次迭代执行 (3)，对 (1) 的每次迭代执行 (2)，你得到 sqrt(N)*2sqrt(N)*N^ 2 = 2N^3，也就是 O(N^3)
关于java - 以下代码的增长顺序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29939873/