c# - 我认为这个片段是 O(n^3) 是对的吗？

Question

collection.Where(i => i.condition)
.ToList()
.ForEach(i => SomeComplicatedOpInvolving_i);

我不是在寻找答案告诉我有更简单的方法来做这件事，只是把它当作一个思想实验。

首先，我认为这是三个循环是否正确？ Where()、ToList() 和 ForEach()?
其次，(假设它是三个循环)我认为这是大 O 表示法中的 n 的 3 次方是否正确？

谢谢大家

Answer 1

不，实际上。我觉得应该是O(n)。

Where() 在 O(n) 中运行(假设 condition 是常量)

ToList() 也遍历 Where 的所有结果，所以也是 O(n)

ForEach() 遍历 ToList 生成的整个列表一次，O(n) 也是如此。我假设 SomeComplicatedOpInvolving_i 不随 i 的数量变化......

这里的关键点是循环不是嵌套的，它们一个接一个地运行 - 所以总运行时间是 3*O(n)，与 O(n) 相同。