Come calcolare la complessità algoritmica dello spazio

Question

Sto rivedendo la lezione sulle strutture dei dati e sull'analisi degli algoritmi e mi viene posta una domanda su come determinarne la complessità spaziale unisci ordinamento E ordinamento velocealgoritmi?

La profondità di ricorsione è solo O(lgn) per il merge-sort di elenchi collegati

La quantità di spazio di archiviazione aggiuntivo necessaria per l'ordinamento rapido contiguo è O(n).

I miei pensieri:

Entrambi usano la strategia divide et impera, quindi immagino che la complessità spaziale dell'ordinamento di unione di elenchi collegati dovrebbe essere la stessa dell'ordinamento rapido contiguo. In realtà opto per O(lgn) perché prima di ogni iterazione o chiamata di ricorsione, l'elenco è metà divisa.

Grazie per eventuali indicazioni.

Answer 1

La profondità di ricorsione nel caso peggiore per Quicksort non è (necessariamente) O(log n), poiché Quicksort non divide i dati "a metà", li divide attorno a un pivot che può o meno essere la mediana.È possibile implementare Quicksort per risolvere questo problema[*], ma presumibilmente l'analisi O(n) riguardava un'implementazione Quicksort ricorsiva di base, non una versione migliorata.Ciò spiegherebbe la discrepanza tra ciò che dici nella citazione e ciò che dici sotto "i miei pensieri".

A parte questo, penso che la tua analisi sia valida: nessuno dei due algoritmi utilizza memoria aggiuntiva oltre a una quantità fissa per livello di ricorsione, quindi la profondità della ricorsione determina la risposta.

Un altro modo possibile per spiegare la discrepanza, suppongo, è che l’analisi O(n) sia semplicemente sbagliata.Oppure, "quicksort contiguo" non è un termine che ho sentito prima, quindi se non significa quello che penso che faccia ("quicksorting di un array"), potrebbe implicare un quicksort che è necessariamente inefficiente in termini di spazio in un certo senso , ad esempio restituire un array allocato invece di eseguire l'ordinamento sul posto.Ma sarebbe sciocco confrontare Quicksort e Mergesort sulla base della profondità di ricorsione del Mergesort rispetto al Mergesort.la dimensione di una copia dell'input per il Quicksort.

[*] Nello specifico, invece di chiamare la funzione in modo ricorsivo su entrambe le parti, la metti in un ciclo.Effettua una chiamata ricorsiva sulla parte più piccola e fai un giro per fare la parte più grande, o in modo equivalente spingi (puntatori a) la parte più grande su una pila di lavoro da fare in seguito e fai un giro per fare la parte più piccola.In ogni caso, ti assicuri che la profondità dello stack non superi mai log n, perché ogni pezzo di lavoro non messo in pila è al massimo la metà della dimensione del pezzo precedente, fino a un minimo fisso (1 o 2 se stai ordinando esclusivamente con Quicksort).

Answer 2

Io non sono molto familiare con il termine "quicksort contigui". Ma quicksort può avere sia O (n) o O (log n) complessità spaziale a seconda di come viene implementato.

Se è implementato come segue:

quicksort(start,stop) {
    m=partition(start,stop);
    quicksort(start,m-1);
    quicksort(m+1,stop);
}

Poi la complessità spaziale è O (n) , non O (log n) come comunemente si crede. Questo perché si sta spingendo nello stack per due volte ad ogni livello, in modo che la complessità spaziale è determinata dalla recurrance:

T(n) = 2*T(n/2)

Supponendo che il partizionamento divide l'array in 2 parti uguali (caso migliore). La soluzione a questo secondo il teorema è T (n) = O (n).

Se sostituiamo la seconda chiamata quicksort con la coda ricorsione nel frammento di codice di cui sopra, allora si ottiene T (n) = T (n / 2) e quindi T (n) = O (log n) (per il caso 2 del il teorema master).

Forse il "quicksort contiguo" si riferisce alla prima attuazione perché le due chiamate Quicksort sono uno accanto all'altro, nel qual caso la complessità spaziale è O (n) .