Complessità asintotica costruzione ABR
Sto studiando i metodi per analizzare gli algoritmi, quindi l'analisi della complessità asintotica
Sono in difficoltà nel calcolo della complessità asintotica della costruzione di un Albero Binario di Ricerca, ora vi spiego come ho ragionato:
l'albero si crea richiamando la funzione per l'inserimento(treeInsert) sugli n elementi, questa funzione impiega tempo O(h) con h indicante l'altezza dell'albero, ora il mio problema è proprio sull'utilizzo di h, infatti eseguendo un algoritmo di complessità Θ(n) per n volte otterrei Θ(n^2), ma in questo caso, usando l'altezza h come variabile indicante la complessità, come dovrei comportarmi?
potrei scrivere semplicemente O(h*n) ma poi come potrei confrontare questo algoritmo con altri algoritmi utilizzanti solo la variabile n?
Sono in difficoltà nel calcolo della complessità asintotica della costruzione di un Albero Binario di Ricerca, ora vi spiego come ho ragionato:
l'albero si crea richiamando la funzione per l'inserimento(treeInsert) sugli n elementi, questa funzione impiega tempo O(h) con h indicante l'altezza dell'albero, ora il mio problema è proprio sull'utilizzo di h, infatti eseguendo un algoritmo di complessità Θ(n) per n volte otterrei Θ(n^2), ma in questo caso, usando l'altezza h come variabile indicante la complessità, come dovrei comportarmi?
potrei scrivere semplicemente O(h*n) ma poi come potrei confrontare questo algoritmo con altri algoritmi utilizzanti solo la variabile n?
Risposte
$h$ è funzione di $n$, cioè del numero di nodi. In particolare per un albero binario è $h = log_2(n)$ (contando la parte intera), oppure può essere funzione del numero di foglie.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo