Qual è la complessità di tempo di .NET list.sort()

Question

Qual è la complessità di tempo di C# 's List<T>.Sort()

Credo che sia O (n)

Ma dopo che ho cercato un sacco, non ho avuto alcun risultato accurato

Answer 1

http://msdn.microsoft.com/en-us/library/b0zbh7b6.aspx

Questo metodo utilizza Array.Sort, che utilizza l'algoritmo QuickSort. Questa implementazione esegue un ordinamento instabile; cioè, se due elementi sono uguali, il loro ordine potrebbe non essere conservato. Al contrario, un ordinamento stabile conserva l'ordine degli elementi uguali.

In media, questo metodo è un'operazione O (n log n), dove n è Count; nel peggiore dei casi è un'operazione O (n^2).

Answer 2

Da the documentation:

In media, questo metodo è un O (n log n), dove n è Conteggio; nel peggiore dei casi è un'operazione O (n^2).

Questo perché utilizza Quicksort. Anche se questo è in genere O (n log n), as mentioned on Wikipedia, "Quicksort è spesso più veloce, in pratica, rispetto agli altri O (n log n) algoritmi"

Answer 3

migliore possibile asintoticamente è O (nlogn)

Answer 4

Aggiunta di alcune informazioni dal recente aggiunta al MSDN su questo argomento, per Framework 4.5, il metodo list.sort utilizza un diverso tipo di strategia a seconda del numero di elementi e partizioni.

Questo metodo utilizza il metodo Array.Sort quale si applica il ordinamento introspettivo come segue:

• Se la dimensione della partizione è meno di 16 elementi, utilizza un algoritmo di ordinamento per inserzione .
• Se il numero di partizioni supera 2 * LogN, dove N è l'intervallo dell'array di input, utilizza un algoritmo Heapsort.
• In caso contrario, utilizza un algoritmo Quicksort.

Questa implementazione esegue un ordinamento instabile; cioè, se due elementi sono uguali, il loro ordine potrebbe non essere conservato. Al contrario, un ordinamento stabile conserva l'ordine di elementi uguali.

In media, questo metodo è un'operazione O (n log n) , dove n è Count; nel peggiore dei casi è un'operazione O (n^2) .