Nel mio codice, Java TreeSet iterazione è il fattore tempo dominante. Osservando il sistema credo che sia O (n) complessità. Qualcuno può verificare questo?Qual è la complessità temporale di iterazione TreeSet?
Penso che fornendo collegamenti all'indietro dal nodo figlio al nodo padre potrei migliorare le prestazioni.
TreeSet l'iterazione è ovviamente O (n), come ci si può aspettare da qualsiasi ragionevole algoritmo di spostamento dell'albero.
Sto pensando che fornendo link all'indietro dal nodo figlio a genitore nodo ho potuto migliorare le prestazioni.
TreeMap (su cui è basato TreeSet) ha già riferimenti parentali. Questo è il metodo che tutto si riduce a:
private Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.right != null) {
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
Penso che il punto chiave sia che non sono solo i nodi foglia che hanno valori collegati. Per 'n' leafs si hanno' O (n log n) 'nodi ma anche' O (n log n) 'valori. In casi reali, mi aspetterei che le operazioni 'O (n)' dominino comunque le operazioni 'O (n log n)'. –
Ho pensato che sarebbe O (n) + O (logn) perché se stai iterando devi prima usare log (n) traversali per trovare la foglia sinistra o più a destra, e poi hai n attraversamenti per camminare l'albero indietro. Quindi hai O (n)? La mia matematica ha senso? –
@john: O (n) + O (log n) è la stessa cosa di O (n) per definizione. –
avete considerato di prendere una copia della TreeSet quando si altera esso? Se il tempo di dominazione viene speso in iterazione TreeSet (anziché modificarlo), la copia di TreeSet su una matrice o ArrayList (solo se alterata) e l'iterazione su questa matrice/ArrayList potrebbe quasi eliminare il costo dell'iterazione TreeSet.
o 'ImmutableSortedSet' di Guava, che è supportato da array. –
Questa domanda non ha senso. Sembra che tu stia dicendo che iterare sul tuo albero è O (n). Questo è il meglio che puoi fare per l'iterazione: la visualizzazione di n elementi richiede tempo O (n). Se vuoi rendere il codice che è dominato dall'iterazione più veloce, devi modificare l'algoritmo in modo che non esegua l'iterazione, ad esempio eseguendo le ricerche nell'albero per tasto (che sarebbe O (log n)) anziché. – babbageclunk