Complessità computazionale delle operazioni TreeSet in Java?

Question

Sto cercando di chiarire alcune cose riguardanti la complessità in alcune delle operazioni di TreeSet. Sul javadoc si dice:

"Questa implementazione fornisce registro garantita (n) Costo tempo per le operazioni di base (aggiungere, rimuovere e contiene)."

Fin qui tutto bene. La mia domanda è ciò che accade sul addAll(), removeAll() ecc Ecco il Javadoc per Set dice:

"Se la raccolta è specificato anche un set , l'operazione addAll efficacemente modifica questo insieme in modo che la sua il valore è l'unione dei due set. "

Sta solo spiegando il risultato logico dell'operazione o sta dando un suggerimento sulla complessità? Voglio dire, se i due set sono rappresentati, ad es. alberi rosso-neri sarebbe meglio unirsi in qualche modo agli alberi piuttosto che "aggiungere" ogni elemento di uno all'altro.

In ogni caso, esiste un modo per combinare due TreeSet in uno con la complessità O (logn)?

Grazie in anticipo. :-)

Answer 1

Si potrebbe immaginare come sarebbe possibile ottimizzare i casi speciali per O(log n), ma il caso peggiore si è avuto modo di essere dove m e n sono il numero di elementi in ogni albero.

Edit:

http://net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm

descrive un algoritmo di caso speciale che può unire gli alberi in O(log(m + n)) ma nota la restrizione: tutti i membri della S1 deve essere inferiore a tutti i membri del S2. Questo è quello che intendevo dire che ci sono ottimizzazioni speciali per casi speciali.

Answer 2

Secondo questo post del blog:
http://rgrig.blogspot.com/2008/06/java-api-complexity-guarantees.html
è O (n log n). Poiché la documentazione non fornisce suggerimenti sulla complessità, potresti voler scrivere il tuo algoritmo se le prestazioni sono fondamentali per te.

Answer 3

Guardando il sorgente java per TreeSet, sembra che se la raccolta passata sia un SortedSet, allora utilizza un algoritmo di tempo O (n). Altrimenti chiama super.addAll, che suppongo produrrà O (n logn).

EDIT - immagino che ho letto il codice troppo veloce, TreeSet può utilizzare solo la O (n) algoritmo se è appoggiando mappa è vuoto

Answer 4

Non è possibile eseguire la fusione degli alberi o partecipare set come in Disjoint- imposta le strutture dati perché non sai se gli elementi nei 2 alberi sono disgiunti. Poiché le strutture di dati hanno conoscenza del contenuto di altri alberi, è necessario verificare se un elemento esiste nell'altro albero prima di aggiungerlo o almeno provare ad aggiungerlo a un altro albero e abortire aggiungendolo se lo si trova su la via. Quindi, dovrebbe essere O (MlogN)