我认为这个片段是 O(n^3) 是正确的吗？
collection.Where(i => i.condition)
.ToList()
.ForEach(i => SomeComplicatedOpInvolving_i);
我并不是在寻找答案来告诉我有一种更简单的方法可以做到这一点，只是将其视为一个思想实验。
首先，我认为这是三个循环，对吗？ Where()、ToList() 和 ForEach()？
其次，（假设是三个循环）我认为这是大O表示法中的n的3次方，对吗？
谢谢大家。
collection.Where(i => i.condition)
.ToList()
.ForEach(i => SomeComplicatedOpInvolving_i);
I'm not looking for answers telling me there is an easier way of doing this, just treat it as a thought experiment.
First up, am I right in thinking that this is three loops? Where(), ToList() and ForEach()?
Second of all, (assuming it is three loops) am I right in thinking this is n to the power of 3 in big O notation?
Thanks everyone.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
不，实际上。我认为应该是O(n)。
Where()的运行时间复杂度为 O(n)（假设condition为常数）ToList()运行Where< 的所有结果/code> 也是如此，所以 O(n) 也是ForEach()运行一次ToList生成的整个列表，所以也是 O(n)。我假设 SomeComplicatedOpInvolving_i 不会随着 i 的数量而缩放...这里的关键点是循环不是嵌套的，它们一个接一个地运行 - 所以总运行时间是 3*O(n )，与 O(n) 相同。
No, actually. I think it should be O(n).
Where()runs in O(n) (assumingconditionis constant)ToList()runs over all the results ofWhereas well, so O(n) tooForEach()runs over the entire list produced byToListonce, so also O(n). I assumeSomeComplicatedOpInvolving_idoesn't scale with the number of i's...The key point here is that the loops aren't nested, they run one after another - so total runtime is 3*O(n), which is the same as O(n).
不，它们不是嵌套循环。是O(n)。
避免使用 ToList()，这会无缘无故地消耗 O(n) 存储空间。查看此博客文章。
No, they are not nested loops. It is O(n).
Avoid using ToList(), that costs O(n) storage for no good reason. Check this blog post.
不，它是
O(n)。如果循环内有循环，则复杂度仅为O(n^3)。No, it's
O(n). It would only beO(n^3)if there was a loop within a loop within a loop.这是
O(n)。由于
Where为O(n)，这意味着Where的成本约为A x n，对于某些 <代码>A。与
ToList和ForEach类似，也是O(n)这意味着它们的成本约为B x n和对于一些。B和一些C分别为 >C x n这意味着总成本大致为：
对于某些
D（我们从来没有真正关心过A、B和C> 是，所以我们也不关心A + B + C是什么，所以只需将其称为D以使我们的方程更简单）。因此这个操作的复杂度是
O(n)。This is
O(n).As
WhereisO(n)this means that the cost ofWhereis approximatelyA x n, for someA.Similarly as
ToListandForEachare alsoO(n)which means their cost is approximatelyB x nandC x nrespective, for someBand someC.This means that the total cost is roughly:
For some
D(we never really cared whatA,BandCwere, so we also don't care whatA + B + Cis, so just call itDto make our equation simpler).Hence this operation is
O(n).它是 O(collection.Size) * O(SomeComplicatedOpInvolving_i)。
It's O(collection.Size) * O(SomeComplicatedOpInvolving_i).
假设 SomeComplicatedOpInvolving 的复杂度为 O(1)，例如，如果您有更多项目，它不会变得更长。
鉴于 那么
该片段是 O(n)
Assuming that SomeComplicatedOpInvolving is O(1), e.g. it does not make longer if you have more items.
Given that
Then the snippet is O(n)