DOMANDA Calcolo Complessità Algoritmo

Fab996

Utente Attivo
177
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: Sei vaccinato? [sondaggio anonimo]

  • Primo ciclo vaccinale completo (1-2 dosi)

    Voti: 457 78.4%
  • Fatta 1a dose, in attesa della 2a

    Voti: 20 3.4%
  • Sono prenotato per la 1a dose

    Voti: 13 2.2%
  • Non so se vaccinarmi

    Voti: 16 2.7%
  • Non ho intenzione di vacciarmi

    Voti: 61 10.5%
  • Fatta anche la terza dose

    Voti: 16 2.7%