Qual è la complessità temporale di un elenco per impostare la conversione?

Ho notato la tabella della complessità temporale delle operazioni di set sul sito ufficiale Python. Ma voglio solo chiedere qual è la complessità temporale di conversione di un elenco per un set, per esempio,Qual è la complessità temporale di un elenco per impostare la conversione?

l = [1, 2, 3, 4, 5] 
s = set(l)

I tipi di sapere che questo è in realtà una tabella hash, ma esattamente come funziona? È O (n) allora?

fonte

2016-01-06 Xuechen Li

Si potrebbe tipo testarlo ... Giusto il tempo per aumentare n. (Non lo so, ma suppongo che dovrebbe essere dato che l'inserimento in una tabella hash è la maggior parte delle volte O (1).). – Trilarion

Grazie, immagino, ero troppo pigro, dovrei abituarmi a usare il modulo timer –

timeit, non il timer –

Sì. L'iterazione su un elenco è O(n) e l'aggiunta di ogni elemento al set di hash è O(1), quindi l'operazione totale è O(n).

fonte

2016-01-06 20:31:37

Nel peggiore dei casi quando si verifica una collisione hash ogni volta, l'inserimento in una tabella hash sarebbe O (n) e O (n^2) nel complesso ma fortunatamente questo non succede quasi mai. – Trilarion

Inoltre, se si dispone di una gestione della memoria molto scarsa o di un hash binning e di un elenco molto grande, le prestazioni non saranno O (n). –

Qual è la complessità temporale di un elenco per impostare la conversione?

risposta

Problemi correlati