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

Question

我在我的项目中使用Linq和Lambda操作，需要按照类的两个属性对列表进行排序。因此，我使用了如下的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);

...

在这个答案中解释了OrderBy()使用的是快速排序算法，因此即使它的平均时间复杂度为O(N*logN)，在最坏情况下，时间复杂度也约为O(N²)。如果ThenBy()方法的最坏时间复杂度也是O(N²)，那么使用这些方法将毫无意义。

ThenBy()方法是否也使用快速排序算法？如果是，这是否意味着对于相同的“v.Value”，“v.Index”会以O(N²)的最坏时间复杂度进行排序？

- tuncay altınpulluk

---

它是O(1)的，因为它仅构造查询，而不执行查询。而且，当查询被执行时，ThenBy不会导致额外的排序，它只是修改已经排队的排序条件。 - user4003407

你不能说它是 O(1)，因为它的执行是不同的。当你需要它的时候才使用它，它的时间复杂度是 O(nlogn)。 - M.kazem Akhgary

@M.kazemAkhgary 我认为这不是一个坏答案（说O(1)），考虑到OP没有展示他对“orderedValues”的操作。 - Phil1970

为什么这很重要？在摘录中，他展示了它是O(nlogn)。 - skyhunter96

Answer 1

LINQ的OrderBy(...).ThenBy(...)...ThenBy(...)方法串联起来形成一个多关键字的单一排序操作（使用多键比较器）。

因此，无论您在链中包含多少ThenBy(Descending)方法，排序操作的时间复杂度都保持典型的快速排序O(N*logN)平均值/ O(N²)最坏情况。当然，您添加的关键字越多，比较两个对象所需的时间就会更长，但是排序操作的复杂性不会改变。

- Ivan Stoev

---

我理解的是，.OrderBy(...).ThenBy(...) 方法链只在单个操作中对列表进行一次排序，并增加了排序时间，但时间复杂度与单个 .OrderBy(...) 相同。谢谢你的回答。 - tuncay altınpulluk

没错，你说得对 :) 实际上这并不一定会增加排序的时间，因为对于多关键字比较器，第二个、第三个等比较器仅在前面的比较器返回相等时才会被调用，也就是取决于你在第一、第二等级上有多少重复的键。在你的例子中，仅当项目具有相等的 Value 时才会比较 Index。 - Ivan Stoev