Il tempo costante e il tempo costante ammortizzato sono effettivamente considerati equivalenti?

Il Tempo Costante ammortizzato può quasi sempre essere considerato equivalente al Tempo Costante, e senza conoscere le specifiche della tua applicazione e il tipo di utilizzo che stai pianificando di fare in questa coda, la maggior parte delle probabilità è che sarai coperto.

Un elenco di array ha il concetto di capacità , che è fondamentalmente uguale alla dimensione / lunghezza / conteggio più grande degli elementi che sono mai stati richiesti finora. Quindi, ciò che accadrà è che all'inizio l'elenco di array continuerà a riallocarsi per aumentare la sua capacità man mano che continui ad aggiungervi elementi, ma ad un certo punto il numero medio di elementi aggiunti per unità di tempo corrisponderà inevitabilmente al numero medio di elementi rimosso per unità di tempo, (altrimenti alla fine si esaurirà comunque la memoria), a quel punto l'array smetterà di riallocarsi e tutti gli accodamenti verranno soddisfatti a O (1) costante.

Tuttavia, tieni presente che, per impostazione predefinita, la rimozione casuale da un elenco di array non è O (1), è O (N), perché gli elenchi di array spostano tutti gli elementi dopo che l'elemento rimosso è a una posizione per prendere il posto dell'oggetto rimosso. Per ottenere O (1) dovrai sostituire il comportamento predefinito per sostituire l'elemento rimosso con una copia dell'ultimo elemento dell'elenco di array e quindi rimuovere l'ultimo elemento, in modo che nessun oggetto possa essere spostato. Ma poi, se lo fai, non hai più una coda.

La domanda sembra chiedere esplicitamente un tempo costante e non un tempo costante ammortizzato . Quindi, rispetto alla domanda citata, no, non sono effettivamente uguali *. Sono comunque nelle applicazioni del mondo reale?

Il tipico problema con costante ammortizzata è che occasionalmente devi pagare il debito accumulato. Quindi, mentre gli inserti sono generalmente costanti, a volte devi soffrire il sovraccarico di reinserire tutto nuovamente quando viene allocato un nuovo blocco.

Dove la differenza tra il tempo costante e il tempo costante ammortizzato è rilevante per un'applicazione dipende dal fatto che questa occasionale velocità lenta sia accettabile. Per un numero molto elevato di domini questo è generalmente ok. Soprattutto se il contenitore ha una dimensione massima effettiva (come cache, buffer temporali, contenitori funzionanti), è possibile pagare in modo efficace solo una volta durante l'esecuzione.

Nelle applicazioni critiche di risposta questi tempi potrebbero essere inaccettabili. Se ti viene richiesto di soddisfare una garanzia di tempi brevi, non puoi fare affidamento su un algoritmo che occasionalmente lo supererà. Ho già lavorato su questi progetti, ma sono estremamente rari.

Dipende anche da quanto è alto questo costo. I vettori tendono a dare buoni risultati poiché il loro costo di riallocazione è relativamente basso. Se si accede alla mappa di hash, tuttavia, la riallocazione può essere molto più alta. Anche se, di nuovo, per la maggior parte delle applicazioni probabilmente vanno bene, in particolare i server con un tempo di vita più lungo con un limite superiore sugli elementi nel contenitore.

* C'è comunque un problema qui. Per fare in modo che un contenitore per scopi generali sia un tempo costante per l'inserimento, è necessario che una delle due cose sia valida:

• Il contenitore deve avere una dimensione massima fissa; o
• puoi supporre che l'allocazione della memoria dei singoli elementi sia costante.

Dipende se stai ottimizzando il throughput o la latenza:

• I sistemi sensibili alla latenza richiedono prestazioni costanti. Per uno scenario del genere, dobbiamo enfatizzare il comportamento nel caso peggiore del sistema. Gli esempi sono sistemi soft real time come i giochi che desiderano ottenere un framerate coerente o server Web che devono inviare una risposta entro un certo periodo di tempo limitato: sprecare i cicli della CPU è meglio che essere in ritardo.
• I sistemi ottimizzati per la velocità effettiva non si preoccupano delle bancarelle occasionali, a condizione che la quantità massima di dati possa essere elaborata a lungo termine. Qui, siamo principalmente interessati alla performance ammortizzata. Questo è generalmente il caso per il numero crunch o altri lavori di elaborazione batch.

Si noti che un sistema può avere componenti diversi che devono essere categorizzati in modo diverso. Per esempio. un moderno processore di testo avrebbe un thread dell'interfaccia utente sensibile alla latenza, ma thread ottimizzati per la velocità effettiva per altre attività come il controllo ortografico o le esportazioni PDF.

Inoltre, la complessità algoritmica spesso non importa quanto penseremmo: quando un problema è limitato a un certo numero, allora le caratteristiche di performance effettive e misurate sono più importanti del comportamento "per grandi n ”.

Se ti viene richiesto un algoritmo di "tempo costante ammortizzato", il tuo algoritmo potrebbe qualche volta richiedere molto tempo. Ad esempio, se si utilizza std :: vector in C ++, un vettore di questo tipo può avere spazio assegnato per 10 oggetti e quando si assegna l'undicesimo oggetto, viene allocato spazio per 20 oggetti, vengono copiati 10 oggetti e aggiunto l'undicesimo, che richiede molto tempo. Ma se aggiungi un milione di oggetti, potresti avere 999.980 operazioni veloci e 20 lente, con un tempo medio veloce.

Se ti viene richiesto un algoritmo di "tempo costante", il tuo algoritmo deve sempre essere veloce, per ogni singola operazione. Ciò sarebbe importante per i sistemi in tempo reale in cui potrebbe essere necessario garantire che ogni singola operazione sia sempre veloce. "Tempo costante" spesso non è necessario, ma è sicuramente non uguale a "tempo costante ammortizzato".