林的大O是什么.在哪里

本文关键字：是什么 在哪里 | 更新日期: 2023-09-27 18:28:54

我正在比较从列表中筛选项目的位置。我不确定是直接做O（n），还是在简单的数据集上使用.Where（）.I made a simple example to test .Where()。有n=100个项，当我在函数BigO()的行上运行调试器时，它正好运行了100次，这让我想到了。其中（）也是O（n）。我无法弄清楚的是，在操作过程中，数据存储在哪里，我不确定这是否会增加复杂性。

我是不是错过了什么，或者是。在哪里（）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();
 }
}

林的大O是什么.在哪里

Where()是O（1）；它实际上没有任何作用。

Where()返回的集合循环为O（n）。。

你看到的O（n）是ToList()的结果，就是O（n
如果将Where()查询传递给O（n2）算法，则会看到回调执行n2次。（假设算法不缓存任何地方）

这称为延迟执行。

对于大多数（如果不是全部的话）LINQ提供商来说，这是正确的；LINQ提供者急切地执行所有调用是没有意义的。

在LINQ to对象的情况下，这假设源集合的枚举器是O（n）
如果你使用的是一个奇怪的集合，它在比O（n）更差的情况下迭代（换句话说，如果它的MoveNext()比O（1）更差），那么Where()将受其约束。

更准确地说，枚举Where()查询的时间复杂性与原始枚举的时间复杂性相同。

类似地，我假设回调是O（1）
如果不是，则需要将回调的复杂性乘以原始枚举的复杂性。

当然取决于集合的来源。

我不同意@SLaks关于算法是O(1)的说法，因为对Where()的查询将继续搜索符合条件的候选者。从这个意义上说，最坏的情况是O(n)和n——在Where子句之前产生整个集合的工作量。

然而，他有一个观点——这取决于产生集合的算法（例如，如果它是一个已经构建的列表，则产生列表的是O(n)，n是集合中的项目数。此外，查找是否匹配的算法不一定是O(1)。如果产生算法是O(n)，匹配算法是O(m)，则时间复杂度是O(n*m)。

以一组整数为例：

int[] test = new int[] {1,2,3,4,5,6,7,8,9,10,7,5,0,1,5,6};

如果您想返回所有至少出现两次的整数，可以使用Where()子句：

test.Where(x => test.Count(y => x == y) >= 2);

该算法将在O(n^2) 中

其次，你也可以建立一个懒惰的设置收集：

public IEnumerable<int> GenerateCollection () {
    //some very complex calculation, here replaced by a simple for loop
    for(int i = 0; i < 150; i++) {
        yield return i;
    }
}

然而，您的算法首先生成列表。因此时间复杂度为O(n)。

但是，请注意，如果在之后迭代整个集合，其中时间复杂性仍然是O(n*m)，而不是O(n*n*m)。这是因为一旦候选人被匹配，就不会重新考虑。

相关文章：