代码片段的渐近分析
我需要找到以下片段的大 O 运行时间：
sum =0;
for (int i=1; i<n; i++) {
for (int j=1; j< n/i; j++) {
sum = sum +j;
}
}
我知道外循环是 O(n) 但我在分析内循环时遇到问题。我认为是 O(log n)。
I need to find the big O running time of the following fragment:
sum =0;
for (int i=1; i<n; i++) {
for (int j=1; j< n/i; j++) {
sum = sum +j;
}
}
I know the outer loop is O(n) but I am having a problem analyzing the inner loop. I think it's O(log n).
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
让我们用这种伪数学风格来写这个。
内部循环（求和）需要
迭代，这使得整个项
根据分配律简化求和：
内部求和在很大程度上类似于
1/x上的积分，它是对数的。所以
O(n log n)是正确的。Let's just write this in this pseudo-mathematical style.
The inner loop (sum) needs
iterations, which makes the whole term
Simplify the sum according to the distributive law:
The inner sum is largely similar to the integral over
1/x, which is logarithmic.So
O(n log n)is right.最好的方法是考虑算法将采取多少步。
如果有 n 个元素，您就知道外循环将至少运行 n 次。所以它必须至少是 O(n)。
每个 i 内循环必须运行多少次？随着 i 的增加，它会增加、保持不变还是减少？
很明显，内循环的步数会随着 i 的增加而减少，更重要的是，它是非线性减少的。所以你知道它并不像 O(n^2) 那么糟糕。
所以它介于 O(n) 和 O(n^2) 之间……对内部循环中的步骤如何减少进行更多分析应该可以帮助您实现这一目标。编辑：...虽然看起来人们已经把它送走了:)
The best approach to this is to consider how many steps the algorithm will take.
If you have n elements, you know that the outer loop is going to run at least n times. So it has to be at least O(n).
How many times does the inner loop have to run for each i? Does it increase, stay the same or decrease as i increases?
It's clear that the number of steps in the inner loop will decrease as i increases, and more importantly, it decreases non-linearly. So you know it isn't as bad as O(n^2).
So it's somewhere between O(n) and O(n^2).... a bit more analysis on how the steps decrease in the inner loop should get you there. EDIT: ... Although it looks like people already gave it away :)
正如 Dave 所说，它的复杂度是 O(n log n)，因为内部循环的复杂度是 O(log n)。
As Dave said, it's O(n log n) because the inner loop is O(log n).