Was ist die zeitliche Komplexität von Linq OrderBy(). ThenBy() Methodenfolge?

Question

Ich verwende Linq und Lambda Operations in meinen Projekten und ich musste eine Liste nach zwei Eigenschaften einer Klasse sortieren. Deshalb habe ich SortiertNach() ThenBy() Methoden wie folgt:.

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

... 

In This Antwort wird erklärt, dass, OrderBy() verwendet Quicksort, also auch wenn es O (N * log N) durchschnittliche Zeit hat Im schlimmsten Fall beträgt die Komplexität der Komplexität etwa 0 (N). Wenn auch die ThenBy() - Methode eine ungünstigste Komplexität von O hat (N), wäre es sinnlos, diese Methoden zu verwenden.

Verwendet ThenBy() auch Quicksort? Wenn ja, bedeutet das, dass für denselben "v.Value" s "v.Index" mit der höchsten Komplexität der Zeit() sortiert wird?

Answer 1

Verfahren Kette LINQ OrderBy(...).ThenBy(...)...ThenBy(...) eine von mehreren Sortierschlüsseln (unter Verwendung von Multi Schlüsselvergleich) einzige Sortieroperation bilden.

So, unabhängig davon, wie viele ThenBy(Descending) Methoden tun sind Sie in der Kette, die typisch die Zeitkomplexität des Sortiervorgang bleibt für QuickSort O (N * log N) Durchschnitt/O (N) im schlechtesten Fall. Natürlich werden mehr Schlüssel, die Sie hinzufügen, wenn Sie zwei Objekte vergleichen, mehr Zeit benötigen, aber die Komplexität der Sortieroperation würde sich nicht ändern.