Tempo di esecuzione dell'operazione di unione impostata

Question

Dati due set A e B, qual è l'algoritmo comune utilizzato per trovare la loro unione e qual è il tempo di esecuzione?

La mia intuizione:

a = set((1, 2, 3))
b = set((2, 3, 5))
union = set()
for el in a:
    union.add(el)

for el in b:
    union.add(el)

Aggiungi i controlli per una collisione, che è O (1), quindi aggiunge l'elemento, che è (??). Questo viene fatto n volte (dove n è | a | + | b |). Quindi questo è O (n * x) dove x è il tempo di esecuzione medio per l'operazione di aggiunta.

È corretto?

Answer 1

Questo dipende molto dall'implementazione. Altri hanno citato insiemi basati su elementi comparabili (hanno un valore inferiore a quello per l'ordinamento) o hashble (hanno una buona funzione hash per l'hash). Un'altra possibile implementazione ha coinvolto "union-find", che supporta solo un sottoinsieme specializzato delle normali operazioni di set ma è molto veloce (l'unione è tempo costante ammortizzato, penso?), Puoi leggere qui

http://en.wikipedia.org/wiki/Union_find

e vedi un'applicazione di esempio qui

http://lorgonblog.spaces.live.com/blog /cns!701679AD17B6D310!220.entry

Answer 2

La complessità di add / find (collisione) dipenderebbe dall'implementazione dell'unione.

Se si utilizza una struttura di dati basata su hashtable, l'operazione di collisione sarà effettivamente costante assumendo una buona funzione di hash.

In caso contrario, aggiungere sarà probabilmente O (Log (N)) per un elenco ordinato / struttura dati ad albero.

Answer 3

Prima risposta: se hai a che fare con insiemi di numeri , potresti implementare un insieme come vettore ordinato di elementi distinti. Quindi potresti implementare l'unione (S1, S2) semplicemente come un'operazione di unione (controllo dei duplicati), che richiede tempo O (n), dove n = somma delle cardinalità.

Ora, la mia prima risposta è un po 'ingenua. E Akusete ha ragione: puoi, e dovresti, implementare un set come una tabella hash (un set dovrebbe essere un contenitore generico e non tutti gli oggetti possono essere ordinati!). Quindi, sia la ricerca che l'inserimento sono O (1) e, come hai intuito, l'unione impiega O (n) tempo.

(Guardando il tuo codice Python) I set Python sono implementati con tabelle hash. Leggi questo interessante thread . Vedi anche questa implementazione che utilizza invece vettori ordinati.

Answer 4

Se puoi usare bitset (ogni bit in un array di int è uguale a un elemento del tuo set), puoi semplicemente camminare sull'array int e sugli OR. Questo ha la complessità O (N) (dove N è la lunghezza dell'array) o O ((m + 31) / 32) dove M è il numero di elementi.