以下程序的时间复杂度是多少？
以下程序的时间复杂度是多少？如何计算复杂度？复杂度的上限和下限是多少？
for(i=n;i<=n^2;i++)
for(j=1;j<=i*log(i);j++)
a[i][j]+=3*i*j;
what's the time complexity of the following program? How to calculate the complexity? What is the upper bound and lower bound of complexity?
for(i=n;i<=n^2;i++)
for(j=1;j<=i*log(i);j++)
a[i][j]+=3*i*j;
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
在外循环中，您将从 n->n^2 开始，即 (n^2-n) 次迭代，即 O(n^2)。
在你的内部循环中，你将从 1->approx (n^2)log(n^2) 开始，即 O((n^2)log(n))
a[i][j] +=3*i*j;是 O(1)，所以你它没有贡献。把它们放在一起，你有 O(n^2 * n^2 * log(n))，即 O(n^4 log(n))
In your outer loop, you're going from n->n^2, which is (n^2-n) iterations which is O(n^2).
In your inner loop, you're going from 1->approx (n^2)log(n^2) which is O((n^2)log(n))
a[i][j]+=3*i*j;is O(1), so you it doesn't contribute.Putting it together, you have O(n^2 * n^2 * log(n)), which is O(n^4 log(n))
迈克的答案是正确的，只是以不同的方式扩展步骤
内部循环：const * i*log(i)
外循环：Sum(i over 1:n^2) of const * i * log(i)
O(algo) = O(Sum(i over 1:n^2) of i * log(i))
From http://en.wikipedia.org/wiki/Summation 我们发现
Sum (i over 1:m) of (i * log(i)) = Theta(m^2*log(m))
代入 m = n^2 我们得到
O(algo) = O(n^2)^2 log(n^ 2) = O(n^4)log(n) （消除 2）（实际上这是算法的 theta）
编辑：我刚刚注意到外循环是 i 超过 n:n^2，但是答案是相同的
Mike's answer is correct, just expanding steps in a different way
Inner loop : const * i*log(i)
Outer loop : Sum(i over 1:n^2) of const * i * log(i)
O(algo) = O(Sum(i over 1:n^2) of i * log(i))
From http://en.wikipedia.org/wiki/Summation we find out that
Sum (i over 1:m) of (i * log(i)) = Theta(m^2*log(m))
Substitute m = n^2 we get
O(algo) = O(n^2)^2 log(n^2) = O(n^4)log(n) (eliminate 2) (Actually that is theta of algo)
EDIT: I just noticed outer loop is i over n:n^2, however answer is same