DOMANDA Calcolo Complessità Algoritmo

Fab996

Utente Attivo
174
5
Devo calcolare nel caso peggiore la complessità di questo algoritmo fornendo Theta,O grande, Omega.

Codice:
FUNZIONE(T) /* T è un albero binario di interi */
    L.head = NULL /* L è una nuova lista (vuota) di interi */
    FUNZ-RIC(T.root,L)
    return L
FUNZ-RIC(v,L)
    if(v==NULL) return
    if(TEST(v))
        AGGIUNGI-IN-CODA(L,v.info)
    FUNZ-RIC(v.left,L)
    FUNZ-RIC(v.right,L)
Supponendo che:
TEST(v) abbia complessità Theta(x), dove x è il numero dei nodi del sottoalbero radicato in v ƒ
AGGIUNGI‐IN‐CODA abbia complessità Theta(x) dove x è la lunghezza della lista

Allora nella prima funzione la prima e ultima riga hanno complessità Theta(1) in quanto istruzioni semplici, poi devo determinare il costo della FUNZ-RIC(), è qui che sto avendo problemi. Ho ragionato nel seguente modo, allora la prima riga ha costo Theta(1), la seconda per definizione Theta(n) e così anche la terza, la quarta e la quinta Theta(1). Poi siccome è una chiamata ricorsiva vuol dire che entro ogni volta nella chiamata n volte (?), quindi ho moltiplicato tutto per Theta(n), quindi prendo l'istruzione che costa di più che è diventata l'if che costa Theta(n^2), quindi il problema ha costo Theta(n^2). Non ho ben capito come trovare il costo di funzione ricorsive e come trovare Omega e O grande...
 

Entra

oppure Accedi utilizzando

Discussioni Simili

Hot del momento