除了与您最喜爱的提供程序相关的LINQ外,这个问题是关于在内存集合中搜索或过滤的。
我知道LINQ(或搜索/过滤扩展方法)适用于实现IEnumerable
或IEnumerable<T>
接口的对象。问题是:由于枚举的本质,每个查询的复杂度至少为O(n)吗?
例如:
var result = list.FirstOrDefault(o => o.something > n);
在这种情况下,除非
list
按照某个标准排序,否则每个算法都至少需要 O(n) 的时间来执行搜索。如果按照'something'
排序,则搜索应该采用二分查找,其时间复杂度为O(log(n))。然而,如果我理解正确,这个查询将通过枚举来解决,因此即使list
之前已经排序,它也应该需要 O(n) 的时间。
- 有什么方法可以在O(log(n))的时间内解决查询吗?
- 如果我想要更好的性能,应该使用Array.Sort和Array.BinarySearch吗?