什么是linq的大O.where？

Question

我正在对从列表中过滤掉项目的位置进行一些比较.我不确定直接这样做是O(n),还是使用.Where().I made a simple example to test .Where()在一个简单的数据集上.有n = 100个项目,当我在函数的行上运行调试器时,BigO()它会正好100次让我认为.Where()也是O(n).我无法弄清楚的是在操作过程中存储数据的位置,我不确定这是否会增加任何增加的复杂性.

我错过了什么,或者是.Where()O(n)？

public class ListerFactory
{

 public class Lister
 {
  bool includeItem { get; set; }
 }

 List<Lister> someList { get; set; }

 public ListerFactory()
 {
  someList = new List<Lister>();
  BuildLister();
 }    

 public void BuildLister()
 {
  for(int i = 0; i < 100; i++)
  {
   var inc = new Lister();
   inc.includeItem = i % 2;
   someList.Add(inc);
  }
  BigO();
 }

 public void BigO()
 {
  someList = someList.Where(thisList => thisList.includeItem == true).ToList();
 }
}

Answer 1

Where()是O(1); 它实际上没有做任何工作.

循环返回的集合Where()是O(n)...

你所看到的O(n)是的结果ToList(),这是为O(n).
如果将Where()查询传递给O(n ²)算法,您将看到回调执行n 次²次.(假设算法不在任何地方缓存)

这称为延迟执行.

大多数(如果不是全部)LINQ提供商都是如此; LINQ提供程序急切地执行所有调用是没有意义的.

对于LINQ to对象,假设源集合的枚举数为O(n).
如果你正在使用一些比O(n)更糟的迭代(换句话说,如果它MoveNext()比O(1)差),那么Where()它将受到限制.

更准确地说,枚举Where()查询的时间复杂度与原始枚举的时间复杂度相同.

同样,我假设回调是O(1).
如果不是,则需要将回调的复杂性乘以原始枚举的复杂性.