Big-O dell'istruzione C++ 'delete [] Q;' O (1) o O (n)?

Question

Il titolo è auto-esplicativo. Domanda molto facile Penso che sia O (n) ma volevo verificare prima della mia finale di domani.

Answer 1

La risposta breve è ... dipende.

Se Q è un puntatore a una matrice di oggetti che hanno distruttori, quindi delete[] Q sarà necessario chiamare tutti quei distruttori. Questo chiamerà O (n) destructors, dove n è il numero di elementi nella matrice. D'altra parte, se Q punta a una matrice di oggetti che non hanno distruttori (ad esempio, int s o semplici struct s), non è necessario chiamare nessun distruttore, che richiede solo O (1) tempo.

Ora si noti che quei distruttori non devono essere eseguiti in O (1) volta ciascuno. Se gli oggetti sono, ad esempio, std::vector oggetti, quindi ogni distruttore a sua volta deve sparare più deallocations. Senza sapere di più su cosa siano questi oggetti, tutto quello che possiamo dire è che se ci sono dei distruttori chiamati, ci saranno 0 distruttori chiamati se i distruttori sono banali e O (n) i distruttori chiamati altrimenti.

Ma questo ignora i dettagli di implementazione di come funziona l'allocatore di heap. È possibile che la deallocazione di un blocco di memoria richieda tempo O (log K), dove K è il numero totale di blocchi allocati, oppure potrebbe richiedere O (1) tempo indipendentemente dal numero di blocchi di memoria presenti, o potrebbe richiedere O (log log K), ecc. Senza sapere come funziona l'allocatore, sinceramente non si può essere sicuri.

Insomma, se ci si concentra esclusivamente sul lavoro necessario per ripulire gli oggetti prima di consegnare il blocco di nuovo alla allocatore di memoria, ci sono O (n) distruttori chiamati se gli oggetti memorizzati sono distruttori e 0 distruttori chiamati in altro modo. Questi distruttori potrebbero richiedere una quantità di tempo non banale da completare. Quindi, c'è il costo di reintrodurre il blocco di memoria nell'allocatore di memoria, che potrebbe impiegare la sua quantità di tempo.

Spero che questo aiuti!

Answer 2

Sono d'accordo con esso dipende, ma lascia parlare solo di liberare X byte di memoria e non preoccuparsi di distruttori.

Alcuni allocatori di memoria mantengono liste libere per oggetti "piccoli" (da 1 a 500 byte). Un inserto in una lista è O (1). Se c'è una lista libera per tutti i thread, allora ha bisogno di acquisire un mutex. L'acquisizione di un mutex di solito comporta fino a un paio di 1000 "spin" e quindi forse una chiamata di sistema (che è molto costosa). Alcuni allocatori dispongono di elenchi gratuiti per thread che utilizzano l'archiviazione locale dei thread, quindi non viene acquisito alcun mutex.

Per un oggetto di dimensioni medie (da 500 a 60000 byte) molti allocatori eseguiranno la coalescenza a blocchi. Cioè controllano se anche i blocchi adiacenti sono liberi e uniscono i 2 o 3 blocchi liberi per creare 1 blocco libero più grande. Coalescing è O (1), ma ancora una volta ha bisogno di acquisire un mutex.

Per blocchi di grandi dimensioni alcuni allocatori ricevono la memoria utilizzando una chiamata di sistema. Quindi liberare la memoria è anche una chiamata di sistema.