Da un po 'di tempo sto lavorando all'ordinamento, ma non riesco a capire a parte queste due domande, sono un po' confuso da qualche parte ... Qualcuno aiuto
a) Quali algoritmi di ordinamento presentano una complessità del caso peggiore diversa rispetto al caso medio?
b) Quali algoritmi di ordinamento hanno una complessità del caso migliore diversa rispetto al caso medio?
L'esempio più ovvio potrebbe essere Quicksort: il suo caso medio è O (N log N) e il caso peggiore è O (N 2 ). Come è normalmente scritto, il caso migliore è O (N log N), ma alcune versioni hanno incluso una pre-scansione per uscire presto quando i dati sono stati ordinati, il che dà una base migliore di O (N), anche se suppongo sia aperto per argomentare che non è più puramente un Quicksort a quel punto.
Non so se lo fa più, ma l'implementazione di qsort nella libreria standard C di Microsoft è stata utilizzata per farlo, principalmente per compensare un'implementazione scadente (usato sempre il primo elemento come pivot) che altrimenti sarebbe stato O (N 2 ) per i dati ordinati.
Qui è una panoramica completa delle complessità.
Alcuni dei più popolari:
L'ordinamento degli inserimenti è un esempio di un algoritmo di ordinamento con un caso migliore del caso medio. Il caso migliore è O (n), il caso medio e il caso peggiore sono O (n²)
La cosa fondamentale qui è riconoscere che l'algoritmo deve prendere scorciatoie per evitare di dover confrontare ogni elemento con ogni altro elemento (che risulterebbe in un algoritmo O (N ^ 2)) ma solo per alcuni degli altri elementi e per farlo di nuovo quando si ordinano questi elementi. Questo è il motivo per cui "dividere il lavoro in pile e gestire ciascuna di queste pile dividendolo in pile e gestire ciascuna di queste pile ecc." Finisce con la complessità di O (N log N).
La parte difficile è scegliere quegli elementi e gestire il lavoro con questi elementi. Scegliere è difficile perché devi scegliere bene per ottenere le subpile ugualmente dimensionate. Gestire è difficile perché non si può passare troppo tempo a spostare le cose se si desidera un algoritmo veloce.
Ad esempio, QuickSort funziona scegliendo un elemento (tradizionalmente chiamato "pivot") e divide il lavoro in due pile. Uno con elementi più piccoli del perno e l'altro più grande. Quindi quicksort ogni pila, e unire le due pile ordinate indietro. Se il pivot è l'elemento più piccolo ogni volta, si finisce con un sotto-mucchio vuoto e un subpile grande con tutti gli elementi tranne il pivot. Ciò provocherà il peggior caso di O (N ^ 2). Se scegli bene, ottieni sub-pali di medie dimensioni e un tempo di esecuzione di O (N log N).
Quindi un modo tipico per scegliere il pivot è di guardare tre valori scelti a caso dalla pila e scegliere quello nel mezzo. Ciò evita almeno il sotto-mucchio vuoto.
Bubble Sort, O (N) nel migliore dei casi, O (N ** 2) nei casi medi e peggiori.
Per ottenere il comportamento O (N), impostare un swapped booleano su false all'inizio di ogni passaggio, impostarlo su true ogni volta che si scambiano due elementi. Se hai scambiato elementi, devi fare un altro passaggio. Questo funziona anche come criterio generale di terminazione, purché i confronti siano deterministici, il che significa che puoi saltare un passaggio di conteggio O (N) prima di iniziare.
Esistono implementazioni che controllano innanzitutto se l'array inizia o termina con una sequenza di elementi in ordine ascendente o discendente e sfrutta il vantaggio se vengono trovati molti di questi elementi. La migliore delle ipotesi è lineare (se l'array viene principalmente ordinato in ordine ascendente o discendente). Ciò che potrebbe essere il caso medio può essere molto discutibile.
Leggi altre domande sui tag algorithms sorting