Qual è la complessità di map/set :: insert se è stato fornito un suggerimento iteratore corretto?

Question

È O (1) o O (logN) ma con un coefficiente più basso?

Se ciò non è specificato, mi piacerebbe almeno conoscere la risposta sulla base di una ragionevole supposizione che la mappa/insieme sia implementata utilizzando un albero rosso-nero o AVL. L'algoritmo generale per inserire un elemento, a mio avviso, è qualcosa di simile:

• trovare il posto giusto - O (log N)
• fare l'inserimento effettivo -?
• riequilibrare l'albero se necessario -?

Ora se mettiamo a disposizione il corretto suggerimento iteratore, quindi il primo passo diventa O (1). Anche le altre fasi sono O (1) o O (logN)?

Answer 1

Lo standard non dice come devono essere implementati i contenitori, quindi non è possibile contare su un RB o un albero AVL. In pratica ... i vincoli della complessità sono tali che non conosco altre implementazioni che corrispondano alla fattura. Ma è nei limiti di complessità che troverai la risposta: “ logaritmico in generale, ma ammortizzato costante se t è inserito subito prima di p. ” Quindi, se il suggerimento è corretto, l'implementazione deve essere tale che l'inserimento sia O (1).

Answer 2

Il primo standard non ha mai detto esattamente quale tipo di struttura dati utilizza per implementare il set. È solo la complessità delle operazioni su di loro che ci aiutano a dirigere verso una sorta di albero di ricerca binario autoequilibrato.

Sì, se si fornisce un suggerimento corretto da inserire posizionando l'iteratore destro, tutti i passaggi verranno ammortizzati O (1) come passaggi 2 e 3 e non dipende da nulla.

Answer 3

• trovare il posto giusto - O (log N)
• fare l'attuale inserimento - O (1), non importa se si tratta di un AVL o RB albero
• riequilibrare l'albero, se necessario - Non conosco l'esatta notazione BIG-O per l'albero AVL, ma per un albero RB è O (1).

Con un suggerimento iteratore, il passo n. 2 (inserimento) e il passo n. 3 (riequilibrio) non subiscono alcun impatto. Fornendo un iteratore, stai solo facendo il passo n. 1 ("trova il posto giusto") da solo, la complessità generale è la stessa.