Input migliori e peggiori per lordinamento dellheap e lordinamento rapido?

heap- Dal momento che il caso migliore e quello peggiore sono gli stessi non importa lordine di input? Il numero di confronti e assegnazioni sarà sempre lo stesso? Immagino che in un ordinamento di heap possa essere lo stesso poiché il lavoro reale viene svolto nellinserimento, ma lordinamento utilizza solo la rimozione del heap max / min? È per questo che?

Il numero di confronti effettuati in realtà può dipendere da lordine in cui vengono forniti i valori. Il fatto che il caso migliore e quello peggiore siano Θ (n log n) – supponendo che tutti gli elementi siano distinti – significa solo che asintoticamente non cè differenza tra i due, sebbene possano differire per un fattore costante. Non ho alcun semplice esempio di questo fuori dalla mia testa, ma credo che tu possa costruire input in cui il numero di confronti differisce di un fattore costante tra due approcci. Tuttavia, poiché la notazione O grande ignora le costanti, ciò non si riflette nellanalisi dei casi migliori e peggiori.

ordinamento rapido – Questo Non lo so per certo. Non sono sicuro di quale sia il caso migliore e il caso peggiore per questo. Se fosse un elenco già ordinato di 10 stringhe, ad esempio, non dovremmo sempre scegliere la stessa quantità di pivot per completare lalgoritmo ricorsivo? Qualsiasi aiuto su questa spiegazione sarebbe davvero di aiuto.

Il numero di pivot scelti è effettivamente lo stesso indipendentemente dallesecuzione dellalgoritmo. Tuttavia, il lavoro svolto per pivot può variare in base al tipo di suddivisioni ottenute. Nel migliore dei casi, il perno scelto ad ogni passaggio finisce per essere lelemento mediano della matrice. Quando ciò accade, ci sono (approssimativamente) n confronti eseguiti allo strato superiore della ricorsione, quindi (approssimativamente) n allo strato successivo perché ci sono due sottoarray di dimensione n / 2, quindi ci sono (approssimativamente) n al livello successivo layer perché ci sono quattro sottoarray di dimensione n / 4, ecc. Poiché ci sono Θ (log n) layer e ogni layer Θ (n) lavoro, il lavoro totale svolto è Θ (n log n). Daltra parte, considera di scegliere il minimo assoluto di ogni array come pivot. Quindi (approssimativamente) n confronti vengono eseguiti sullo strato superiore, quindi (approssimativamente) n – 1 nello strato successivo, quindi (approssimativamente) n – 2 nel successivo, ecc. La somma 1 + 2 + 3 + … + n è Θ (n ² ), quindi il caso peggiore.

Spero che questo aiuti!

Commenti

• Signore, qual è il caso migliore di heapsort nlogn? Se consideriamo che tutti gli elementi sono identici, il costo sarebbe solo literazione di tutti gli elementi dellarray e nessuno spostamento verso lalto fino alla radice. Quindi dovrebbe essere omega (n) secondo me.
• Questo è un buon punto. Stavo assumendo elementi distinti, quindi aggiornerò questa risposta.

Poiché nessuno “s affrontato davvero heapSort ancora:

Supponendo che tu stia usando un heap max rappresentato come un array e inserendo i tuoi elementi max allindietro nel tuo array di output / nel retro del tuo array se “lo stai facendo sul posto , linput del caso peggiore per heapSort è qualsiasi input che ti costringe a “rimpicciolire” o ricaricare ogni volta che rimuovi un elemento. Ciò accade ogni volta che provi a ordinare un set senza duplicati. Sarà comunque Θ (n log n), come ha detto templatetypedef.

Questa proprietà implica che il caso migliore di heapSort è quando tutti gli elementi sono uguali (Θ (n), poiché non è necessario reheapificare dopo ogni rimozione, il che richiede tempo log (n) poiché laltezza massima dellheap è log (n)). È una specie di caso schifoso / poco pratico, motivo per cui il vero caso migliore per heapsort è Θ (n log n).

Commenti

• Il tuo punto sul caso schifoso e impraticabile è stato appena chiesto nella mia classe di algoritmi. (attenti alle domande trabocchetti.) Naturalmente, ‘ sono ancora daccordo con il tuo punto. ( e come risultato ho sbagliato la mia risposta XD)

• Ordinamento rapido

  Caso peggiore: $ \ mathcal {O} (n ^ 2) $ . Supponiamo che lelemento pivot sia sempre lelemento più a destra: inserisci già un elenco ordinato con elementi $ n $ . Quindi ogni partizionamento porta a un elenco con elementi $ n-1 $ e un elenco con elementi $ 0 $ . Anche se scegli lelemento pivot in modo casuale , puoi comunque essere sfortunato e scegliere sempre il valore massimo nellelenco.

  Sia $ T (n) $ il numero di confronti quicksort richiede di ordinare un elenco con elementi $ n $ . Caso peggiore: \ begin {align} T (n) = & T (n-1) + n & \ text {($ T (n-1) $ ricorsivo, $ n $ a partion)} \\ = & \ frac {n (n + 1) } {2} \ in \ mathcal {O} (n) \ end {align}

  Caso migliore: $ \ mathcal {O} (n \ log n) $ . Se lelemento pivot viene scelto in modo tale da partizionare lelenco in modo uniforme:

  \ begin {align} T (n) = & 2 \ T \ left (\ frac {n} {2} \ right) + n & (\ text {2 volte $ \ frac {n} { 2} $ ricorsivo, $ n $ alla partizione)} \\ \ in & \ mathcal {O} (n \ log n) & (\ text {master theorem}) \ end {align}

• Ordinamento heap

  Il caso peggiore e la complessità dei casi migliori per lordinamento di heap sono entrambi $ \ mathcal {O} (n \ log n) $ . Pertanto, lordinamento dellheap necessita di confronti $ \ mathcal {O} (n \ log n) $ per qualsiasi array di input. Complessità dellordinamento dellheap:

  \ begin {align} & \ mathcal {O} (n) & (\ text {build $ (1, n) $ heap}) \\ + & \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i – \ log 1) & (\ text {build $ (1, j) $ heap}) \\ = & \ mathcal {O} (n) + \ sum_ {i = 1} ^ {n} \ mathcal {O} (\ log i) & (\ text {regola del quoziente logaritmo}) \\ = & \ mathcal {O} (n \ log n) & \ left (\ sum_ {i = 1} ^ {n} \ log i < \ sum_ {i = 1} ^ {n} \ log n = n \ log n \ right) \ end {align }

Commenti

• Non hai ‘ t ha risposto a tutte le ‘ domande dellOP, quindi risponderò a una che ti sei persa; lordinamento heap non ‘ utilizza sempre lo stesso numero di confronti per un dato numero di elementi. Il caso peggiore è $ a \, n \ log n $ e il caso migliore è $ b \, n \ log n $, dove $ a > b $.
• Tieni inoltre presente che la variante a tre vie ha lineare il caso migliore per linput di un singolo elemento.