对数组求和的大 O 估计
如果我有一个包含 100 万个整数的数组。 总结起来被认为是 O(n)，因为我必须执行 n-1 次加法运算。 正确的 ？
If I have an array of 1 million integers.
Summing it up is considered O(n) because I have to perfom n-1 add operations.
Correct ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果您可以在 O(1) 时间内添加两个元素，那么对 n 个元素求和需要 O(n)，是的。如果他们可能需要更长的时间，那就不会。例如，如果所有元素都是无符号 32 位整数，但您想要精确的总和（不是总和 mod 232），那么它可能与 n · (232 − 1) 在这种情况下求和将花费 O(n log n)。
If you can add two elements in O(1) then summing n elements takes O(n), yes. If they may take longer, then no. For example, if all of the elements are unsigned 32-bit integers but you want the exact sum (not the sum mod 232) then it may be as large as n · (232 − 1) in which case summing will take O(n log n).
是的。这是完全正确的。
当然，也可能有特殊情况，会比较少。某些方法可以使其更小，但这些方法的开销比加法更大。
例如，如果您知道值是从 1 到 n，则时间复杂度为 O(1)，因为您可以计算 n*(n+1)/2。但一般情况是 O(n)。
Yes. That's exactly correct.
Of course, there may be special cases where it's less. And certain methods could make it smaller, but those methods have a greater overhead than addition.
For example, if you know the values are from 1 to n, that's O(1) because you can compute n*(n+1)/2. But the general case is O(n).
是的，因为求和所用的时间是元素
n数量的直接变化。Yes, because the time used for summing is direct variation to the number of elements
n.