我是否正确地认为这个片段是O(n ^ 3)？

Question

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

我不是在寻找答案,告诉我有一种更简单的方法可以做到这一点,只需将其视为思想实验.

首先,我是否认为这是三个循环？Where(),ToList()和ForEach()？
第二,(假设它是三个循环)我是否正确地认为这是大O符号中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) 相同。