Limite inferiore per l'ordinamento per confronto

Question

Oggi stavo leggendo un articolo di Julienne Walker sull'ordinamento - Eternally Confuzzled - The Art of Sorting e una cosa ha attirato la mia attenzione. Io non capisco la parte in cui l'autore dimostra che per l'ordinamento in confronto siamo limitati da Ω (N · il login N) limite inferiore

Lower limiti non sono così evidenti. Il limite più basso possibile per la maggior parte degli algoritmi di ordinamento è Ω (N · log N). Questo perché la maggior parte degli algoritmi di ordinamento utilizza il confronto degli articoli per determinare l'ordine relativo degli articoli. Qualsiasi algoritmo che ordina per confronto avrà un limite inferiore minimo di Ω (N · log N) perché un albero di confronto viene utilizzato per selezionare una permutazione che è ordinata. Un albero di confronto per i tre numeri 1, 2 e 3 possono essere facilmente costruiti:

      1 < 2 

      1 < 3      1 < 3 

    2 < 3   3,1,2  2,1,3   2 < 3 

1,2,3 1,3,2       2,3,1  3,2,1 

Notate come ogni elemento viene confrontato con ogni altro elemento, e che ogni risultato di percorso in una permutazione valida dei tre elementi. L'altezza dell'albero determina il limite inferiore dell'algoritmo di ordinamento. Perché ci deve essere come tante foglie quante sono le permutazioni per l'algoritmo sia corretta, la più piccola altezza possibile dell'albero confronto è log N!, che equivale a Ω (N · log N) .

sembra essere un molto ragionevole fino a quando l'ultima parte (in grassetto) che io non capisco - come log N! è equivalente a Ω (N · registro N). Devo mancare qualcosa ai miei corsi CopmSci e non posso ottenere l'ultima transizione. Non vedo l'ora di ricevere aiuto per questo o per qualche link ad altre prove che siamo limitati Ω (N · log N) se usiamo l'ordinamento per confronto.

Answer 1

Non hai perso nulla dalla classe CompSci. Quello che ti sei perso era la lezione di matematica. La pagina Wikipedia di Stirling's Approximation mostra che log n! è asintoticamente n log n + termini di ordine inferiore.

Answer 2

• N! < N^N
• ∴ log N! < log (N^N)
• ∴ log N! < N * log N

Con questo, è possibile dimostrare θ (log N!) = O (N log N). Provare lo stesso per Ω è lasciato come esercizio per il lettore, o una domanda per mathematics stackexchange o theoretical computer science stackexchange.

Answer 3

La mia prova preferita di questo è molto elementare.

N! = 1 * 2 * .. * N - 1 * N

Possiamo un limite inferiore molto semplice facendo finta che la prima metà di quei prodotti non esistano, e quindi che la seconda metà sia tutta solo N/2 .

(N/2)^(N/2) < = N!

log ((N/2)^(N/2) = N/2 * log (N/2) = N/2 * (log (N) - 1) = O (n log n)

Quindi, anche quando prendi solo la seconda metà dell'espressione e fai finta che tutti questi fattori non siano più grandi di N/2, sei ancora nel territorio di O (n log n) per un limite inferiore, e questo è super elementare Potrei convincere uno studente della scuola media di questo, non posso nemmeno ricavare da solo la formula di Stirling