Linq OrderBy().ThenBy() 方法序列的时间复杂度是多少？

Question

我在我的项目中使用 Linq 和 Lambda 操作，我需要根据 class 的两个属性对列表进行排序。因此，我使用了 OrderBy().ThenBy() 方法如下：

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);

...

在This答案中解释说，OrderBy()使用Quicksort，所以即使它有O(N*logN)的平均时间复杂度，最坏的情况下，时间复杂度在O( N²)。如果 ThenBy() 方法的最差时间复杂度为 O(N²)，那么使用这些方法将毫无意义。

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

Answer 1

LINQ OrderBy(...).ThenBy(...)...ThenBy(...) 方法链通过多个排序键（使用多键比较器）形成一个单排序操作。

因此，无论您在链中包含多少 ThenBy(Descending) 方法，排序操作的时间复杂度仍然是快速排序的典型时间复杂度 O(N*logN) 平均 / O(N²) 最坏的情况。当然你加的键越多，比较两个对象会耗费更多的时间，但是排序操作的复杂度是不会变的。

Linq OrderBy().ThenBy() 方法序列的时间复杂度是多少？

What is the time complexity of Linq OrderBy().ThenBy() method sequence?

c#

linq

big-o

lambda