Какова временная сложность последовательности Linq OrderBy(). ThenBy()?

Я использую Linq и Lambda Operations в своих проектах, и мне нужно было отсортировать List по двум свойствам класса. Поэтому я использовал методы 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() использует Quicksort, поэтому даже если он имеет среднюю временную сложность O (N * logN), для худшего случай, временная сложность вокруг O (N 2). Если также метод ThenBy() имеет худшую временную сложность O (N 2), было бы бессмысленно использовать эти методы.

Используется ли метод ThenBy() Quicksort? Если да, означает ли это, что для тех же "v.Value" s "v.Index" сортируются с наихудшей сложностью O (N 2)?

Ответы

Ответ 1

Цепочка методов LINQ OrderBy(...).ThenBy(...)...ThenBy(...) формирует операцию сортировки одиночная с помощью нескольких ключей сортировки (с использованием сопоставления с несколькими ключами).

Таким образом, независимо от того, сколько методов ThenBy(Descending) вы включаете в цепочку, временная сложность операции сортировки остается типичной для QuickSort O (N * logN) в среднем /O (N 2) худший случай. Конечно, больше добавленных ключей, сравнение двух объектов займет больше времени, но сложность операции сортировки не изменится.