我最近开始大量使用LINQ，但我没有看到任何一种LINQ方法的运行时复杂性.显然，这里有很多因素在起作用，所以让我们把讨论限制在普通的IEnumerable LINQ对象提供程序上.此外，让我们假设作为 Select 器/变异器等传入的任何Func都是廉价的O(1)操作.
显然，所有单次通过操作(Select、Where、Count、Take/Skip、Any/All等)将是O(N)，因为它们只需要遍历序列一次；尽管即使这样也会受到懒惰的影响.
对于更复杂的操作来说，情况更加模糊；set-like操作符(Union、Distinct、Except等)在默认情况下使用GetHashCode(afaik)，因此假设它们在内部使用哈希表似乎是合理的，一般来说，这些操作也是O(n).那么使用IEqualityComparer的版本呢？
OrderBy需要排序，所以我们很可能看到的是O(n logn).如果已经分类了呢？如果我说OrderBy().ThenBy()，并为两者提供相同的密钥，怎么样？
我可以看到GroupBy个(和Join个)使用排序或散列.到底是哪一个？
Contains在List上是O(n)，但在HashSet上是O(1)——LINQ是否判断底层容器以查看它是否可以加快速度？
而真正的问题是——到目前为止，我一直相信这些行动是有效的.然而，我能指望吗？例如，STL容器明确规定了每个操作的复杂性.是否有类似的LINQ性能保证.NET库规范？
更多问题(回复 comments ):
我没有真正考虑过开销，但我没想到会有太多简单的Linq-to-Objects.CodingHorror的帖子谈到了Linq-to-SQL，在那里我可以理解解析查询和创建SQL会增加成本-对象提供者也有类似的成本吗？如果是这样，那么使用声明性语法还是函数语法会有什么不同呢？