La complessità temporale delle operazioni di set python?

Question

Qual è la complessità temporale di ciascuna delle operazioni di Python nella notazione Big O?

Sto usando Python set type per un'operazione su un numero elevato di elementi. Voglio sapere come le prestazioni di ciascuna operazione saranno influenzate dalle dimensioni del set. Ad esempio, add, e il test per l'adesione:

myset = set() 
myset.add('foo') 
'foo' in myset 

Googling intorno non si è alzato tutte le risorse, ma sembra ragionevole che la complessità temporale per l'attuazione set di Python sarebbe stato considerato con attenzione.

Se esiste, un collegamento a qualcosa come this sarebbe fantastico. Se niente di simile è là fuori, allora forse possiamo risolverlo?

Marchi extra per la ricerca della complessità temporale di tutte le operazioni di set.

Answer 1

L'operazione in deve essere indipendente dalla dimensione del contenitore, ad es. O (1) - data una funzione hash ottimale. Questo dovrebbe essere quasi true per le stringhe Python. Le stringhe di hashing sono sempre critiche, Python dovrebbe essere intelligente lì e quindi puoi aspettarti risultati quasi ottimali.

Answer 2

Secondo Python wiki: Time complexity, set è implementato come hash table. Quindi puoi aspettarti di cercare/inserire/eliminare nella media O (1). A meno che il fattore di carico della tabella hash non sia troppo alto, si verificano collisioni e O (n).

P.S. per qualche ragione affermano O (n) per un'operazione di cancellazione che sembra un errore di battitura.

P.P.S. Questo è vero per CPython, pypy è un different story.