LINQ方法的运行时复杂性（Big-O）有什么保证？

3回答

当年话下

保证非常非常少，但有一些优化：使用索引访问扩展方法，比如ElementAt，Skip，Last或者LastOrDefault，将检查底层式工具与否IList<T>，让你得到O（1）访问，而不是O（N）。该Count方法检查ICollection实现，以便该操作是O（1）而不是O（N）。Distinct，GroupBy Join我相信set-aggregation方法（Union，Intersect和Except）也使用散列，所以它们应该接近O（N）而不是O（N²）。Contains检查ICollection实现，因此如果底层集合也是O（1），它可能是O（1），例如a HashSet<T>，但这取决于实际的数据结构，并且不能保证。散列集覆盖了该Contains方法，这就是它们为O（1）的原因。OrderBy 方法使用稳定的快速排序，因此它们是O（N log N）平均情况。我认为这涵盖了大多数（如果不是全部）内置扩展方法。实际保证很少; Linq本身将尝试利用高效的数据结构，但编写可能效率低下的代码并不是免费的。

0 0

胡说叔叔

我早就知道如果枚举是一个.Count()返回。.CountIList但是我总是有点疲惫有关Set操作的运行时间复杂度：.Intersect()，.Except()，.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()和.Except()。扰流板警报：它们也具有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;   }}

0 0

慕的地8271018

所有你能真正依赖的是，Enumerable方法是针对一般情况编写的，不会使用朴素算法。可能有第三方的东西（博客等）描述了实际使用的算法，但这些并不是官方的，也不是STL算法所保证的。为了说明，这里是Enumerable.Count来自System.Core 的反映源代码（由ILSpy提供）：// System.Linq.Enumerablepublic 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;     }}正如您所看到的，它需要付出一些努力来避免简单地枚举每个元素的天真解决方案。

0 0