Qual è la complessità asintotica nel trovare il tempo lineare dell'Elemento Successivo Maggiore?

Question

stavo leggendo un algoritmo per ottenere il Next Greater Element per ogni elemento di un array.

Il sito afferma che il loro codice viene eseguito O(n) tempo, ma non riesco a capirlo.

Un attraversamento completo della matrice da sinistra a destra avrà un costo O(n), oltre al quale possono esserci più operazioni push/pop su ciascun indice mentre attraversiamo l'elenco.

Sebbene le operazioni push/pop richiedano un tempo costante, se vengono chiamate in media diciamo m volte per elemento dell'indice, avremmo O(m) come il costo delle operazioni push/pop su ciascun indice, portando a O(mn) come costo totale, ora poiché il numero totale di operazioni push/pop dovrebbe essere approssimativamente (o forse esattamente) uguale a n, possiamo dirlo mn è approssimativamente (o forse esattamente) uguale a n implicandolo m è una costante.

La mia giustificazione è giusta?

Non ho ancora la giusta chiarezza nel mio ragionamento, qualcuno potrebbe fornire una spiegazione migliore oltre a convalidare/invalidare la mia giustificazione?

Answer 1

Pseudo-codice copiato qui per comodità:

1. Spingi il primo elemento da impilare.
   
2. Scegli il resto degli elementi uno per uno e segui i seguenti passaggi in loop.
   
   1. Contrassegna l'elemento corrente come Prossimo.
      
   2. Se lo stack non è vuoto, estrai un elemento dallo stack e confrontalo Prossimo.
      
   3. Se next è maggiore dell'elemento spuntato, allora Prossimo è l'elemento successivo più grande per l'elemento estratto.
      
   4. Continua a estrarre dallo stack mentre l'elemento estratto è più piccolo di Prossimo. Prossimo diventa l'elemento successivo più grande per tutti questi elementi spuntati
      
   5. Se Prossimo è più piccolo dell'elemento spuntato, quindi spingere indietro l'elemento spuntato.
      
   6. Spingere Prossimo nello stack [questo passaggio manca nello pseudo-codice]
3. Una volta terminato il ciclo del passaggio 2, estrai tutti gli elementi dallo stack e stampa -1 come elemento successivo.

Viene eseguito il ciclo esterno O(n) volte.

Chiaramente, con l'eccezione del lavoro svolto per gli elementi spuntati non respinti (passaggio n. 4, meno l'ultimo elemento gestito), il resto dell'iterazione del ciclo è a tempo costante.

Pertanto, qualsiasi elemento che continua a essere estratto e reinserito nello stack sarà già incluso nel tempo costante di ogni iterazione in cui viene estratto e reinserito.

Tutto ciò che rimane sono i tempi in cui gli elementi vengono estratti e non respinti, ma chiaramente questo può accadere solo una volta per ciascun elemento, quindi questo spiega, in totale, O(n) tempo di esecuzione.

Dal momento che non duplichiamo mai gli elementi nello stack (spingiamo ogni elemento dall'array una volta, quindi lo spingiamo di nuovo solo dopo averlo estratto) non possono esserci più di n elementi nello stack, quindi il passaggio finale richiede al massimo O(n) tempo.

Quindi il tempo di esecuzione totale è O(n + n + n) = O(n).

---

Un modo alternativo di ragionare al riguardo:

Eseguiamo un massimo di 2 operazioni push durante ogni iterazione del ciclo (che ci sono n Di).

Quindi ce ne sono al massimo 2n operazioni push, e quindi anche al massimo 2n operazioni pop (non possiamo pop elementi che non sono stati inseriti).

Eseguiamo una quantità costante di lavoro per operazione push/pop e inoltre eseguiamo una quantità costante di lavoro per iterazione del ciclo (ignorando il lavoro svolto per operazione push/pop), quindi il tempo di esecuzione totale è O(n + 4n) = O(n).

Answer 2

Tu forse hai m operazioni per iterazione di n Ma m è ancora una costante ed è indipendente da n.

Il numero di operazioni push/pop è costante per ogni iterazione di n quindi non influenzano la complessità temporale dell'algoritmo.