我正在比较从列表中筛选项目的位置。我不确定是直接做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();
}
}
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)
。这是因为一旦候选人被匹配,就不会重新考虑。