[Generico] complessità di un algoritmo

[flavio<Integer>]

Salve ho un dubbio sul calcolo della complessita di questo algoritmo:

Codice:

if(v==NULL) return
if(v.left != NULL)
 AGGIUNGI-IN-TESTA(L,v.info)
 FUNZ-RIC(v.left,L)
if(v.right != NULL)
 AGGIUNGI-IN-CODA(L,v.info)
 FUNZ-RIC(v.right,L)

secondo me ha complessita $ Theta (n) $ perchè AGGIUNGI-IN-TESTA ha complessità $ Theta (1) $ e AGGIUNGI-IN-CODA ha complessità $ Theta (n) $ .
Però non sono molto sicuro che sia in ragionamento giusto. Potreste gentilmente aiutarmi?

Grazie in anticipo.

[apatriarca]

Cos'è FUNZ-RIC? Il codice che hai postato?

[flavio<Integer>]

è uno pseudocodice. Questo è un esercizio in cui va calcolata la complessità di un codice dato in questo modo, quindi FUNZ-RIC non ha un vero e proprio significato ma sta ad indicare che si tratta di una funzione ricorsiva.

[apatriarca]

Che sia pseudocodice è chiaro. Tuttavia credo che sarebbe stato più corretto scriverlo come una funzione se il codice viene richiamato in modo ricorsivo. Suppongo insomma che il codice sia equivalente a questo codice python:

Codice:

def funz_ric(v, lst):
    if v: return
    if v.left:
        lst.insert(v.info, 0)
        funz_ric(v.left, lst)
    if v.right:
        lst.append(v.info)
        funz_ric(v.right, lst)


Dal tuo tentativo di soluzione posso in realtà dedurre che L è una lista concatenata (quella che ho usato nel codice è implementata diversamente ma era solo per capirsi). Siccome la funzione è ricorsiva la complessità andrà calcolata scrivendo la corrispondente equazione di ricorrenza. E' corretta questa interpretazione? Oppure si deve considerare la funzione ricorsiva come una funzione di complessità conosciuta?

[flavio<Integer>]

grazie per la tua risposta e mi scuso perchè in effetti sono stato poco chiaro nel porgere la domanda.Il testo completo dell' esercizio è questo:

Discuti la complessità computazionale della seguente procedura nel caso peggiore fornendo O‐grande,
Omega e Theta in funzione del numero n di elementi dell’albero.

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(v.left != NULL)
        AGGIUNGI-IN-TESTA(L,v.info)
        FUNZ-RIC(v.left,L)
    if(v.right != NULL)
        AGGIUNGI-IN-CODA(L,v.info)
        FUNZ-RIC(v.right,L)

Supponi che AGGIUNGI‐IN‐TESTA abbia complessità Theta(1) e AGGIUNGI‐IN‐CODA abbia complessità
Theta(x) dove x è la lunghezza della lista

e l'esercizio andrebbe risolto senza usare equazioni di ricorrenza.

Grazie ancora

[apatriarca]

Il caso peggiore si ha quando l'albero è semplicemente una lista connessa tramite i puntatori a sinistra. In questo caso viene eseguito AGGIUNGI-IN-TESTA per ogni nodo dell'albero e la complessità è quindi lineare.

Il caso peggiore è invece quando si sceglie sempre il lato destro. In questo caso abbiamo che la complessità è uguale alla somma delle complessità di AGGIUNGI-IN-CODA dove la lista ha dimensione uguale al numero di nodi visitato fino a questo punto. Si tratta quindi del numero triangolare che ha complessità quadratica.

La complessità media è molto più complicata da calcolare ma in questo caso non è necessario. E' chiaro?

[flavio<Integer>]

Sei stato chiarissimo. Grazie mille!