我是否认为这个片段是O（n^3）？

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

我不是在寻找答案，告诉我有一个更简单的方法来做到这一点，只是把它当作一个思想实验。我是否认为这个片段是O（n^3）？

首先，我认为这是三个循环吗？ Where(),ToList()和ForEach()？
其次，（假设它是三个循环）我是否认为这对大3中的3的幂是n？

谢谢大家。

来源

2011-09-01 Adam Naylor

它不取决于SomeComplicatedOpInvolving_i做什么？ – AndrewC

如果我们假设'collection'的类型是'IEnumerable '，那么由于延迟加载，它只会是O（2 * n）。 – ebb

仅仅因为你不想使用一个普通的'foreach（）'循环就不要'ToList'，因为创建和填充列表是目前为止这个片段中最密集的操作。 – Dykam

不，实际上。我认为它应该是O（n）。

Where()运行在O（n）的（假设condition是恒定的）

ToList()超过Where所有运行的结果一样，所以O（n）的太

ForEach()运行在由所产生的整个列表ToList一次，所以也是O（n）。我假设SomeComplicatedOpInvolving_i不与我的数量成比例...

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

来源

2011-09-01 10:02:29 Peter

+1考虑到子表达的复杂性，并明确指出可以写出涉及3的复杂性，但这并不重要。 – delnan

如果你想迂腐，ToList不是O（n），因为它有时需要复制才能增长:-) – xanatos

准确地说，我一直在寻找的解释感谢你抽出时间来分解它。这是我被混淆的3 * n和n^3。 –

不，它们不是嵌套循环。它开着）。

避免使用ToList（），这会导致无法正常使用O（n）存储。检查这个blog post。

来源

2011-09-01 10:00:41

不，这是O(n)。如果循环内的循环内存在循环，则只有O(n^3)。

来源

2011-09-01 10:00:54

这是O(n)。

由于Where是O(n)这意味着Where的成本大约是A x n，对于某些A。

同样作为ToList和ForEach也O(n)这意味着它们的成本大约是B x n和C x n各自，对于一些B和一些C。

这意味着总成本大致是：

(A x n) + (B x n) + (C x n) 
= (A + B + C) x n 
= D x n

对于一些D（我们从来没有真正关心什么A，B和C人，所以我们也不在乎什么A + B + C是，所以才打电话它D使我们的等式更简单）。

因此该操作是O(n)。

来源

2011-09-01 10:03:12 Justin

collection.Where(i => i.condition) // is O(n) where n is the size of collection 
.ToList() // is O(m) where m is the number if items with i.condition true 
.ForEach(i => SomeComplicatedOpInvolving_i); // O(m) where m is the number if items with i.condition true

假设SomeComplicatedOpInvolving是O（1），例如，如果你有更多的物品，它不会更长。

鉴于

when m is never bigger then n, then 
O(n) + O(m) + O(m) == O(n)

然后片断是O（n）

来源

2011-09-01 10:03:29

这是O（collection.Size）* O（SomeComplicatedOpInvolving_i）。

来源

2011-09-01 10:05:40

我是否认为这个片段是O（n^3）？

回答

相关问题