是作业上的,求一个通用的方法。
计算以下代码在最坏情况下的运行时间。
int sum = 0;
for (int i = 0; i*i < N; i++)
for (int j = 0; j < i*i; j++)
sum++;
答案是 N^3/2,谁能帮我解决这个问题?
有没有通用的计算方法?
This is what I thought:
when i = 0, sum++ will be called 0 time
when i = 1, sum++ will be called 1 time
when i = 2, sum++ will be called 4 times
...
when i = i, sum++ will be called i^2 times
so the worst time will be
0 + 1 + 4 + 9 + 16 + ... + i^2
但是接下来呢??我迷路了...
最佳答案
您想计算最内层循环将运行多少次。
外层将从 i = 0 运行到 i = sqrt(N)(因为 i*i < N)。 对于外部迭代的每次迭代,内部迭代将运行 i^2 次。
因此内部运行的总次数是:
1^2 + 2^2 + 3^2 + ... + sqrt(N)^2
有一个公式:
1^2 + 2^2 + ... + k^2 = k(k+1)(2k+1) / 6 = O(k^3).
在你的例子中 k = sqrt(N)。
总复杂度为 O(sqrt(N)^3) = O(N^(3/2))
。
关于algorithm - 最坏情况运行时间计算,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11948322/