LINQ方法的运行时复杂性（Big-O）有什么保证？
我最近开始使用LINQ相当多，而且我还没有看到任何LINQ方法的运行时复杂性。 很明显，这里有很多因素，所以让我们把讨论限制在纯IEnumerable LINQ-to-Objects提供程序中。 此外，假设任何作为select器/增变器等传入的Func都是便宜的O（1）操作。
似乎很明显，所有的单程操作（ Select ， Where ， Count ， Take/Skip ， Any/All等）都是O（n），因为他们只需要走一次序列; 虽然这是懒惰。
对于更复杂的操作，情况会更加恶劣。 集合类运算符（ Union ， Distinct ， Except等）默认使用GetHashCode （afaik），所以假设他们在内部使用哈希表似乎是合理的，也使得这些操作O（n）一般来说。 那么使用IEqualityComparer的版本呢？
OrderBy需要sorting，所以很可能我们看O（n log n）。 如果它已经分类？ 如果我说OrderBy().ThenBy()并提供相同的密钥？
我可以看到GroupBy （和Join ）使用sorting或哈希。 这是哪个？
Contains在List O（n），但O（1）在HashSet – 是否LINQ检查底层容器，看看它是否可以加快速度？
而真正的问题 – 到目前为止，我一直坚信这个操作是高性能的。 但是，我可以在这个银行？ 例如，STL容器清楚地说明了每个操作的复杂性。 .NET库规范中的LINQ性能有没有类似的保证？
更多的问题（回复评论）：
没有真正考虑开销，但我没想到对于简单的Linq-to-Objects来说还有很多。 CodingHorror文章谈论Linq到SQL，在那里我可以理解parsing查询，并使SQL会增加成本 – 对象提供者也有类似的成本？ 如果是这样，如果你使用声明性或function性语法，它是不同的？
有很less的保证，但有几个优化：
-
使用索引访问的扩展方法（如
ElementAt，Skip，Last或LastOrDefault）将检查基础types是否实现IList<T>，以便获得O（1）访问而不是O（N）。 -
Count方法检查ICollection实现，所以这个操作是O（1）而不是O（N）。 -
Distinct，GroupByJoin，我也相信集合聚合方法（Union，Intersect和Except）使用散列，所以它们应该接近O（N）而不是O（N²）。 -
Contains对ICollection实现的检查，因此如果底层集合也是O（1）（如HashSet<T>），则它可能是O（1），但这取决于实际的数据结构并且不能保证。 哈希集重写Contains方法，这就是为什么他们是O（1）。 -
OrderBy方法使用稳定的快速sorting，因此它们是O（N log N）平均情况。
我认为这涵盖了大部分（如果不是全部）内置的扩展方法。 确实有很less的性能保证。 Linq本身将尝试利用高效的数据结构，但是写入潜在的低效代码并不是一个自由通行证。
所有你可以真正存储的是Enumerable方法是写得很好的一般情况下，不会使用天真的algorithm。 有可能是第三方的东西（博客等），描述了实际使用的algorithm，但这些都不是官方的或STLalgorithm的保证。
为了说明，这里是来自System.Core的Enumerable.Count的reflection源代码（由ILSpy提供）：
// System.Linq.Enumerable public static int Count<TSource>(this IEnumerable<TSource> source) { checked { if (source == null) { throw Error.ArgumentNull("source"); } ICollection<TSource> collection = source as ICollection<TSource>; if (collection != null) { return collection.Count; } ICollection collection2 = source as ICollection; if (collection2 != null) { return collection2.Count; } int num = 0; using (IEnumerator<TSource> enumerator = source.GetEnumerator()) { while (enumerator.MoveNext()) { num++; } } return num; } }
正如你所看到的，为了避免简单列举每一个元素的简单解决scheme，需要做一些努力。
我早就知道.Count()返回.Count如果枚举是一个IList 。
但是我总是对Set操作的运行时复杂.Intersect()到厌倦： .Intersect() .Union() 。
这里是.Intersect()的反编译的BCL（.NET 4.0 / 4.5）实现。
private static IEnumerable<TSource> IntersectIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer) { Set<TSource> set = new Set<TSource>(comparer); foreach (TSource source in second) // O(M) set.Add(source); // O(1) foreach (TSource source in first) // O(N) { if (set.Remove(source)) // O(1) yield return source; } }
结论：
- 性能是O（M + N）
- 当集合已经被设置时，实现没有利用。 （它可能不一定是直接的，因为使用的
IEqualityComparer<T>也需要匹配。）
为了完整.Union() ，下面是.Union()和.Union()的实现。
扰stream警报：它们也具有O（N + M）的复杂性。
private static IEnumerable<TSource> UnionIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer) { Set<TSource> set = new Set<TSource>(comparer); foreach (TSource source in first) { if (set.Add(source)) yield return source; } foreach (TSource source in second) { if (set.Add(source)) yield return source; } } private static IEnumerable<TSource> ExceptIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer) { Set<TSource> set = new Set<TSource>(comparer); foreach (TSource source in second) set.Add(source); foreach (TSource source in first) { if (set.Add(source)) yield return source; } }
我刚爆发了reflection器，当Contains被调用时，他们检查底层types。
public static bool Contains<TSource>(this IEnumerable<TSource> source, TSource value) { ICollection<TSource> is2 = source as ICollection<TSource>; if (is2 != null) { return is2.Contains(value); } return source.Contains<TSource>(value, null); }
正确的答案是“这取决于”。 它取决于底层的IEnumerable是什么types。 我知道对于一些集合（如实现ICollection或IList的集合），有特殊的代码path被使用，但是实际的实现不保证做任何特殊的事情。 例如我知道ElementAt（）有一个可索引集合的特殊情况，类似于Count（）。 但总的来说，你可能应该承担最糟糕的O（n）performance。
一般来说，我不认为你会find你想要的性能保证types，但如果你遇到一个linq运算符的特定性能问题，你总是可以为你的特定集合重新实现它。 还有很多博客和扩展项目，将Linq扩展到对象以添加这些性能保证。 检查索引LINQ ，它扩展并添加到操作集中以获得更多性能优势。
