In che modo la creazione di un heap può essere O (n) la complessità temporale?

Qualcuno può aiutare a spiegare in che modo build un mucchio può essere O (n) complessità?

L’inserimento di un elemento in un heap è O(log n) e l’inserto viene ripetuto n / 2 volte (il resto è foglie e non può violare la proprietà heap). Quindi, questo significa che la complessità dovrebbe essere O(n log n) , penserei.

In altre parole, per ogni elemento che “ammucchia”, ha il potenziale di dover filtrare una volta per ogni livello per lo heap fino ad ora (che è il livello log n).

Cosa mi manca?

Penso che ci siano diverse domande sepolte in questo argomento:

  • Come si implementa buildHeap in modo che venga eseguito in tempo O (n) ?
  • Come si mostra che buildHeap viene eseguito in tempo O (n) se implementato correttamente?
  • Perché la stessa logica non funziona per rendere l’ordinamento dell’heap eseguito nel tempo O (n) anziché in O (n log n) ?

Spesso, le risposte a queste domande si concentrano sulla differenza tra siftUp e siftDown . Fare la scelta corretta tra siftUp e siftDown è fondamentale per ottenere prestazioni O (n) per buildHeap , ma non fa nulla per aiutare a capire la differenza tra buildHeap e heapSort in generale. Infatti, le implementazioni corrette di buildHeap e heapSort useranno solo siftDown . L’operazione siftUp è necessaria solo per eseguire inserimenti in un heap esistente, quindi dovrebbe essere utilizzata per implementare una coda di priorità usando un heap binario, ad esempio.

Ho scritto questo per descrivere come funziona un heap massimo. Questo è il tipo di heap in genere utilizzato per l’ordinamento heap o per una coda di priorità in cui i valori più alti indicano una priorità più alta. È anche utile un heap minimo; ad esempio, quando si recuperano elementi con chiavi intere in ordine crescente o stringhe in ordine alfabetico. I principi sono esattamente gli stessi; basta cambiare l’ordinamento.

La proprietà heap specifica che ciascun nodo in un heap binario deve essere grande almeno quanto entrambi i suoi figli. In particolare, ciò implica che l’elemento più grande nell’heap si trova alla radice. Spostarsi verso il basso e setacciare sono essenzialmente la stessa operazione in direzioni opposte: spostare un nodo offensivo finché non soddisfa la proprietà heap:

  • siftDown scambia un nodo che è troppo piccolo con il suo figlio più grande (spostandolo in basso) finché non è grande almeno quanto entrambi i nodes sotto di esso.
  • siftUp scambia un nodo che è troppo grande con il suo genitore (spostandolo così verso l’alto) fino a quando non è più grande del nodo sopra di esso.

Il numero di operazioni richieste per siftDown e siftUp è proporzionale alla distanza che il nodo potrebbe dover spostare. Per siftDown , è la distanza dalla parte inferiore dell’albero, quindi siftDown è costoso per i nodes nella parte superiore dell’albero. Con siftUp , il lavoro è proporzionale alla distanza dalla cima dell’albero, quindi siftUp è costoso per i nodes nella parte inferiore dell’albero. Sebbene entrambe le operazioni siano O (log n) nel peggiore dei casi, in un heap, solo un nodo è in alto mentre metà dei nodes giace nello strato inferiore. Quindi non dovrebbe essere troppo sorprendente il fatto che se dovessimo applicare un’operazione a ogni nodo, preferiremmo siftDown su siftUp .

La funzione buildHeap accetta una matrice di elementi non ordinati e li sposta finché tutti soddisfano la proprietà heap, producendo in tal modo un heap valido. Ci sono due approcci che si potrebbero prendere per buildHeap usando le operazioni siftUp e siftDown che abbiamo descritto.

  1. Inizia nella parte superiore dell’heap (l’inizio dell’array) e chiama siftUp su ciascun elemento. Ad ogni passaggio, gli elementi precedentemente setacciati (gli elementi che precedono l’elemento corrente nell’array) formano un heap valido, e setacciando l’elemento successivo su lo colloca in una posizione valida nell’heap. Dopo aver setacciato ciascun nodo, tutti gli elementi soddisfano la proprietà heap.

  2. Oppure, vai nella direzione opposta: inizia alla fine della schiera e vai indietro in avanti. Ad ogni iterazione, si spazia un object verso il basso finché non si trova nella posizione corretta.

Entrambe queste soluzioni produrranno un heap valido. La domanda è: quale implementazione per buildHeap è più efficiente? Non sorprendentemente, è la seconda operazione che utilizza siftDown .

Sia h = log n rappresenta l’altezza dell’heap. Il lavoro richiesto per l’approccio siftDown è dato dalla sum

 (0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1). 

Ogni termine nella sum ha la distanza massima che un nodo all’altezza data dovrà spostare (zero per il livello inferiore, h per la radice) moltiplicato per il numero di nodes a quell’altezza. Al contrario, la sum per chiamare siftUp su ogni nodo è

 (h * n/2) + ((h-1) * n/4) + ((h-2)*n/8) + ... + (0 * 1). 

Dovrebbe essere chiaro che la seconda sum è più grande. Il primo termine è hn / 2 = 1/2 n log n , quindi questo approccio ha la complessità al massimo O (n log n) . Ma come proviamo che la sum per l’approccio siftDown sia effettivamente O (n) ? Un metodo (ci sono altre analisi che funzionano anche) consiste nel trasformare la sum finita in una serie infinita e quindi usare la serie di Taylor. Possiamo ignorare il primo termine, che è zero:

Serie di Taylor per buildHeap complessità

Se non sei sicuro del motivo per cui ognuno di questi passaggi funziona, ecco una giustificazione per il processo in parole:

  • I termini sono tutti positivi, quindi la sum finita deve essere inferiore alla sum infinita.
  • La serie è uguale a una serie di potenze valutata a x = 1/2 .
  • Quella serie di potenze è uguale a (a volte costanti) la derivata della serie di Taylor per f (x) = 1 / (1-x) .
  • x = 1/2 è nell’intervallo di convergenza di quella serie di Taylor.
  • Pertanto, possiamo sostituire la serie di Taylor con 1 / (1-x) , differenziare e valutare per trovare il valore della serie infinita.

Poiché la sum infinita è esattamente n , concludiamo che la sum finita non è più grande ed è quindi, O (n) .

La prossima domanda è: se è ansible eseguire buildHeap in tempo lineare, perché l’ordinamento heap richiede tempo O (n log n) ? Bene, l’ordinamento dell’heap consiste in due fasi. Per prima cosa, chiamiamo buildHeap sull’array, che richiede O (n) tempo se implementato in modo ottimale. Il prossimo passo è quello di eliminare ripetutamente l’elemento più grande nell’heap e metterlo alla fine dell’array. Poiché eliminiamo un elemento dall’heap, c’è sempre uno spot aperto subito dopo la fine dell’heap in cui è ansible archiviare l’elemento. Quindi, l’ordinamento heap ottiene un ordine ordinato rimuovendo successivamente il successivo elemento più grande e inserendolo nell’array partendo dall’ultima posizione e spostandosi verso la parte anteriore. È la complessità di quest’ultima parte che domina in un mucchio di specie. Il ciclo sembra piace questo:

 for (i = n - 1; i > 0; i--) { arr[i] = deleteMax(); } 

Chiaramente, il ciclo esegue O (n) volte ( n – 1 per essere precisi, l’ultimo elemento è già sul posto). La complessità di deleteMax per un heap è O (log n) . In genere viene implementato rimuovendo la radice (l’elemento più grande rimasto nell’heap) e sostituendolo con l’ultimo elemento nell’heap, che è una foglia e quindi uno degli elementi più piccoli. Questa nuova radice quasi certamente violerà la proprietà heap, quindi devi chiamare siftDown finché non lo sposti in una posizione accettabile. Ciò ha anche l’effetto di spostare l’elemento successivo più grande fino alla radice. Nota che, contrariamente a buildHeap dove per la maggior parte dei nodes chiamiamo siftDown dal fondo dell’albero, ora chiamiamo siftDown dalla cima dell’albero su ogni iterazione! Anche se l’albero si sta restringendo, non si restringe abbastanza velocemente : l’altezza dell’albero rimane costante fino a quando non si rimuove la prima metà dei nodes (quando si cancella completamente lo strato inferiore). Poi per il prossimo quarto, l’altezza è h – 1 . Quindi il lavoro totale per questo secondo stadio è

 h*n/2 + (h-1)*n/4 + ... + 0 * 1. 

Nota l’interruttore: ora il caso di lavoro zero corrisponde a un nodo singolo e il caso di lavoro h corrisponde a metà dei nodes. Questa sum è O (n log n) proprio come la versione inefficiente di buildHeap implementata usando siftUp. Ma in questo caso, non abbiamo scelta, dal momento che stiamo cercando di ordinare e abbiamo bisogno che il successivo elemento più grande venga rimosso successivamente.

In sintesi, il lavoro per l’ordinamento dell’heap è la sum dei due stadi: O (n) tempo per buildHeap e O (n log n) per rimuovere ciascun nodo in ordine , quindi la complessità è O (n log n) . Puoi provare (usando alcune idee dalla teoria dell’informazione) che per un ordinamento basato sul confronto, O (n log n) è il meglio che puoi sperare comunque, quindi non c’è motivo di essere deluso da questo o aspettarsi che il tipo di heap raggiunga il O (n) ha tempo vincolato a buildHeap .

La tua analisi è corretta. Tuttavia, non è stretto.

Non è davvero facile spiegare perché build un heap è un’operazione lineare, dovresti leggerlo meglio.

Una grande analisi dell’algoritmo può essere vista qui .


L’idea principale è che nell’algoritmo heapify costo heapify effettivo non sia O(log n) per tutti gli elementi.

Quando viene chiamato heapify , il tempo di esecuzione dipende dalla misura in cui un elemento può spostarsi verso il basso nella struttura ad albero prima che il processo termini. In altre parole, dipende dall’altezza dell’elemento nell’heap. Nel peggiore dei casi, l’elemento potrebbe scendere fino al livello foglia.

Contiamo il lavoro svolto livello per livello.

Al livello più basso, ci sono 2^(h) nodes, ma non chiamiamo heapify su nessuno di questi, quindi il lavoro è 0. Al livello successivo ci sono 2^(h − 1) nodes, e ognuno potrebbe verso il basso di 1 livello. Al 3 ° livello dal basso, ci sono 2^(h − 2) nodes e ognuno potrebbe spostarsi verso il basso di 2 livelli.

Come puoi vedere, non tutte le operazioni di heapify sono O(log n) , questo è il motivo per cui stai ricevendo O(n) .

Intuitivamente:

“La complessità dovrebbe essere O (nLog n) … per ogni elemento che” ammucchiamo “, ha il potenziale di dover filtrare una volta per ogni livello per lo heap fino ad ora (che è il livello log n).”

Non proprio. La tua logica non produce uno stretto vincolo: stima la complessità di ogni heapify. Se costruito dal basso verso l’alto, l’inserimento (heapify) può essere molto inferiore a O(log(n)) . Il processo è il seguente:

(Passaggio 1) I primi n/2 elementi vanno nella riga inferiore dell’heap. h=0 , quindi heapify non è necessario.

(Passaggio 2) I successivi n/2 2 elementi vanno sulla riga 1 in alto dal basso. h=1 , heapify filtri 1 livello in basso.

(Fase i ) I successivi n/2 i elementi entrano nella riga i dal basso. h=i , i filtri heapify si livellano.

(Step log (n) ) L’ultimo n/2 log 2 (n) = 1 elemento va nella riga log(n) alto dal basso. h=log(n) , abbassa i livelli di h=log(n) dei filtri in basso.

AVVISO: che dopo il punto uno, 1/2 degli elementi (n/2) sono già presenti nell’heap e non è nemmeno stato necessario richiamare l’heap una volta. Inoltre, si noti che solo un singolo elemento, la radice, in realtà incorre nella complessità completa del log(n) .


teoricamente:

I passaggi totali N per creare un heap di dimensione n , possono essere scritti matematicamente.

All’altezza di i , abbiamo mostrato (sopra) che ci saranno n/2 i+1 elementi n/2 i+1 che devono chiamare heapify, e sappiamo che heapify in altezza è O(i) . Questo da:

inserisci la descrizione dell'immagine qui

La soluzione all’ultima sumtoria può essere trovata prendendo la derivata di entrambi i lati della ben nota equazione delle serie geometriche:

inserisci la descrizione dell'immagine qui

Infine, collegando x = 1/2 all’equazione precedente si ottiene 2 . Inserendo questo nella prima equazione si ottiene:

inserisci la descrizione dell'immagine qui

Pertanto, il numero totale di passaggi è di dimensione O(n)

Sarebbe O (n log n) se hai costruito l’heap inserendo ripetutamente gli elementi. Tuttavia, è ansible creare un nuovo heap in modo più efficiente inserendo gli elementi in ordine arbitrario e quindi applicando un algoritmo per “accumularli” nell’ordine corretto (a seconda del tipo di heap, ovviamente).

Vedi http://en.wikipedia.org/wiki/Binary_heap , “Costruire un heap” per un esempio. In questo caso si lavora essenzialmente dal livello inferiore dell’albero, scambiando i nodes padre e figlio fino a quando le condizioni dell’heap sono soddisfatte.

Mentre crei un mucchio, ti dico che stai adottando un approccio dal basso verso l’alto.

  1. Prendi ogni elemento e confrontalo con i suoi figli per verificare se la coppia è conforms alle regole dell’heap. Quindi, le foglie vengono incluse nell’heap gratuitamente. Questo perché non hanno figli.
  2. Andando verso l’alto, lo scenario peggiore per il nodo appena sopra le foglie sarebbe un confronto (al massimo sarebbero confrontati con una sola generazione di bambini)
  3. Andando più in alto, i loro genitori immediati possono al massimo essere paragonati a due generazioni di bambini.
  4. Continuando nella stessa direzione, avrai log (n) confronti per la radice nello scenario peggiore. e registra (n) -1 per i suoi figli immediati, registra (n) -2 per i loro figli immediati e così via.
  5. Quindi riassumendo tutto, si arriva su qualcosa come log (n) + {log (n) -1} * 2 + {log (n) -2} * 4 + ….. + 1 * 2 ^ {( logn) -1} che non è altro che O (n).

Come sappiamo, l’altezza di un heap è log (n) , dove n è il numero totale di elementi. Lo rappresenta come h
Quando eseguiamo un’operazione di heapify, quindi gli elementi al livello più alto ( h ) non si sposteranno nemmeno in un singolo passaggio.
Il numero di elementi al secondo livello ( h-1 ) è 2 h-1 e possono spostarsi al massimo 1 livello (durante l’heap).
Allo stesso modo, per il livello , abbiamo 2 elementi i che possono muoversi in posizioni alte.

Quindi il numero totale di mosse = S = 2 h * 0 + 2 h-1 * 1 + 2 h-2 * 2 + … 2 0 * h

S = 2 h {1/2 + 2/2 2 + 3/2 3 + … h / 2 h } ———————– ————————– 1
questa è la serie AGP , per risolvere questa divisione da entrambi i lati per 2
S / 2 = 2 h {1/2 2 + 2/2 3 + … h / 2 h + 1 } ———————– ————————– 2
sottrarre l’equazione 2 da 1 a
S / 2 = 2 h { 1/2 + 1/2 2 + 1/2 3 + … + 1/2 h + h / 2 h + 1 }
S = 2 h + 1 { 1/2 + 1/2 2 + 1/2 3 + … + 1/2 h + h / 2 h + 1 }
ora 1/2 + 1/2 2 + 1/2 3 + … + 1/2 h sta diminuendo GP la cui sum è minore di 1 (quando h tende all’infinito, la sum tende a 1). In ulteriori analisi, prendiamo un limite superiore della sum che è 1.
Questo dà S = 2 h + 1 {1 + h / 2 h + 1 }
= 2 ore + 1 + h
~ 2 ore + h
come h = log (n) , 2 h = n

Quindi S = n + log (n)
T (C) = O (n)

In caso di costruzione dell’heap, partiamo dall’altezza, logn -1 (dove logn è l’altezza dell’albero di n elementi). Per ogni elemento presente all’altezza ‘h’, andiamo al massimo fino a (logn -h) in altezza.

  So total number of traversal would be:- T(n) = sigma((2^(logn-h))*h) where h varies from 1 to logn T(n) = n((1/2)+(2/4)+(3/8)+.....+(logn/(2^logn))) T(n) = n*(sigma(x/(2^x))) where x varies from 1 to logn and according to the [sources][1] function in the bracket approaches to 2 at infinity. Hence T(n) ~ O(n) 

Gli inserimenti successivi possono essere descritti da:

 T = O(log(1) + log(2) + .. + log(n)) = O(log(n!)) 

Con approssimazione stellare, n! =~ O(n^(n + O(1))) n! =~ O(n^(n + O(1))) , quindi T =~ O(nlog(n))

Spero che questo aiuti, il modo ottimale O(n) sta usando l’algoritmo di heap di build per un determinato set (l’ordine non ha importanza).

@bcorso ha già dimostrato la prova dell’analisi della complessità. Ma per il bene di coloro che stanno ancora imparando l’analisi della complessità, devo aggiungere questo:

La base del tuo errore originale è dovuta a un’interpretazione errata del significato dell’istruzione, “l’inserimento in un heap richiede tempo O (log n)”. L’inserimento in un heap è in effetti O (log n), ma devi riconoscere che n è la dimensione dell’heap durante l’inserimento .

Nel contesto dell’inserimento di n oggetti in un heap, la complessità dell’inserimento ith è O (log n_i) dove n_i è la dimensione dell’heap come all’inserimento i. Solo l’ultimo inserimento ha una complessità di O (log n).

Mi piace molto la spiegazione di Jeremy west …. un altro approccio che è davvero facile da capire è qui http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity

poiché, buildheap dipende dall’utilizzo dell’heapify e viene utilizzato l’approccio shiftdown che dipende dalla sum delle altezze di tutti i nodes. Quindi, per trovare la sum di altezza dei nodes che è data da S = sum da i = 0 a i = h di (2 ^ i * (hi)), dove h = logn è l’altezza dell’albero che risolve s, otteniamo s = 2 ^ (h + 1) – 1 – (h + 1) poiché, n = 2 ^ (h + 1) – 1 s = n – h – 1 = n- logn – 1 s = O (n), e così la complessità di buildheap è O (n).

“Il limite di tempo lineare dell’heap di costruzione può essere mostrato calcolando la sum delle altezze di tutti i nodes nell’heap, che è il numero massimo di linee tratteggiate.Per l’albero binario perfetto di altezza h contenente N = 2 ^ ( h + 1) – 1 nodo, la sum delle altezze dei nodes è N – H – 1. Quindi è O (N). ”

Fondamentalmente, il lavoro viene fatto solo su nodes non foglia mentre si costruisce un heap … e il lavoro svolto è la quantità di swap verso il basso per soddisfare la condizione dell’heap … in altre parole (nel peggiore dei casi) la quantità è proporzionale all’altezza del nodo … tutto sumto la complessità del problema è proporzionale alla sum delle altezze di tutti i nodes non fogliari .. che è (2 ^ h + 1 – 1) -h-1 = nh-1 = Sopra)

Prova di O (n)

La dimostrazione non è di fantasia, e piuttosto semplice, ho solo dimostrato il caso di un albero binario completo, il risultato può essere generalizzato per un albero binario completo.

pensa di fare un errore Dai un’occhiata a questo: http://golang.org/pkg/container/heap/ Costruire un heap isn’y O (n). Tuttavia, l’inserimento è O (lg (n). Sto assumendo che l’inizializzazione sia O (n) se si imposta una dimensione heap b / c l’heap deve allocare spazio e impostare la struttura dati. Se si hanno n elementi da mettere nel mucchio allora sì, ogni inserto è lg (n) e ci sono n elementi, quindi ottieni n * lg (n) come hai detto