Qual è la complessità temporale dell'albero trasversale, sono sicuro che deve essere ovvio, ma il mio povero cervello non può risolverlo in questo momento.Qual è la complessità temporale dell'albero trasversale?
Dipende dal tipo di attraversamento che si sta eseguendo e dall'algoritmo, ma in genere è O (n) dove n è il numero totale di nodi nell'albero. L'implementazione canonica ricorsiva della prima traversata di profondità, consumerà la memoria (in pila) nell'ordine del livello più profondo, che su un albero bilanciato sarebbe log (n).
È vero per un albero n-ario? Ho una struttura dati che è un albero di massima profondità 4 e per attraversarlo il mio amico usa 3 per cicli, e sta dicendo che il suo algoritmo funziona in tempo "O (n^3)", ma credo che sia in esecuzione in n' tempo, 'n' sta nel numero totale di nodi nell'albero – Nicholas
@Nocholas, sei corretto e il tuo amico ha torto. È su). – Uri
Non sarebbe solo n per un albero con n nodi?
Visiti ogni albero una volta, vero? Quindi direi che è lineare.
Immagino che dovrebbe essere un albero con "n nodi" e non "n foglie". – aamadmi
Hai ragione, errata terminoligy :) – Nanne
@Nanne Con l'algoritmo giusto è effettivamente una complessità lineare nel tempo (visitando ogni nodo una volta), ma potrebbe non avere ancora una complessità lineare nello spazio. Come usare la pila. – Tim
È lineare Art of Programming Vol 1 pagina 326 – new299
È quella l'arte della programmazione per computer di Knuth? Sto cercando di trovare questo per dare ad un amico un buon esempio che per un albero n-ary è lineare. – Nicholas
sì "L'arte della programmazione del computer" di Knuth – new299