Linq OrderBy().ThenBy()方法序列的时间复杂度是多少? [英] What is the time complexity of Linq OrderBy().ThenBy() method sequence?

问题描述

我在项目中使用Linq和Lambda Operations，我需要根据类的两个属性对列表进行排序.因此，我使用了OrderBy().ThenBy()方法，如下所示:

I am using Linq and Lambda Operations in my projects and I needed to sort a List according to two properties of a class. Therefore, I used OrderBy().ThenBy() methods as below:

class ValueWithIndex{
    public long Value;
    public int Index;
}
...

List<ValueWithIndex> valuesWithIndex = new List<ValueWithIndex>();

for (int i = 0; i < A.Length; i++){
    ValueWithIndex vi = new ValueWithIndex();
    vi.Value = A[i];
    vi.Index = i;
    valuesWithIndex.Add(vi);
}
var orderedValues = valuesWithIndex.OrderBy(v => v.Value).ThenBy(v => v.Index);

...

在此答案中，解释说，OrderBy()使用Quicksort，即使它具有O(N * logN)平均时间复杂度，在最坏的情况下，时间复杂度约为O(N ² ).如果ThenBy()方法的时间复杂度也为O(N ² )，则使用这些方法毫无意义.

In This answer, it is explained that, OrderBy() uses Quicksort, so even if it has O(N*logN) average time complexity, for the worst case, time complexity is around O(N²). If also ThenBy() method has a worst time complexity of O(N²), it would be pointless to use these methods.

那么ThenBy()方法也使用Quicksort吗?如果是，是否意味着对于相同的"v.Value"，"v.Index"以最差的时间复杂度O(N ² )排序?

Is ThenBy() method use Quicksort, too? If yes, does it mean that for the same "v.Value"s, "v.Index"es are sorted with O(N²) worst time complexity?

推荐答案

LINQ OrderBy(...).ThenBy(...)...ThenBy(...)方法链通过多个排序键(使用多关键比较器).

The LINQ OrderBy(...).ThenBy(...)...ThenBy(...) method chain form a single sort operation by multiple sort keys (using multi key comparer).

因此，无论您在链中包含多少个ThenBy(Descending)方法，排序操作的时间复杂度都保持了QuickSort O(N * logN)平均值/O(N ^{2 )最坏的情况.当然，您添加的键更多，比较两个对象将花费更多时间，但是排序操作的复杂性不会改变.}

Thus, regardless of how many ThenBy(Descending) methods do you include in the chain, the time complexity of the sort operation stays the typical for QuickSort O(N*logN) average / O(N²) worst case. Of course more keys you add, comparing two objects will take more time, but the complexity of the sort operation would not change.

这篇关于Linq OrderBy().ThenBy()方法序列的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！