Calcolo della complessità

[Perfo]

Ciao a tutti :)
Dovrei calcolare la complessità di un algoritmo in java.
Praticamente ho fatto il calcolo ma ho grossi dubbi in queste porzioni di codice:


while (testa != coda) {
for (t = coda; t != null && t.struttura.frequenza > agg; t = t.prec);
}

Qui il dubbio è quante volte iterano il ciclo while e quello for, dato che non è determinabile con un numero....


void trasforma(Nodo p) {
if (p.sx == null && p.dx == null){
p.dx = stream[p.segno+128];
stream[p.segno+128] = p;
}
else {
trasforma(p.sx);
trasforma(p.dx);
}
}


Qui invece quante volte viene chiamata la ricorsione?
:help:
Aiutatemi se potete, vi ringrazio già da ora :)

[jappilas]

l' algoritmo su cosa opera? su una lista ?
in ogni caso , a meno che non entri in ciclo infinito per aver omesso/errato qualche verifica di condizione, si eseguirà la trasforma sugli elementi dello stream che sono per definizione, finiti (è un numero finito la dimensione della memoria, è un numero finito la banda eventuale di trasmissione dello stream, è un numero finito, il tempo che vivi davanti allo schermo per ricevere pacchetti dello stream, nel caso questo appaia come un "continous feed".. )

il caso estremo (numero di operazioni nel caso peggiore) dovrebbe essere, data una finestra di N elementi,
<n. di operazioni della transform> x N x (N-1)
nel caso la transform chiami se stessa altre n-1 volte , per ogni elemento dello stream contenuto nella finestra
che , visto che il primo termine è una costante e N-1 (circa) N, non vorrei sbagliare ma mi sembra diventi O(N^2)

[franksisca]

per il doppio ciclo innestato quoto O(n^2), mentre per la ricorsione attento alla dimensione dell'input

[Perfo]

Ciao a tutti :)

Grazie Mille :ave:

Cmq l'alg opera su una lista con la quale implemento un albero binario.

Il codice che è contenuto in "while testa != coda" serve per raggruppare tanti nodi in un unico albero.
posto il codice completo del ciclo
while (testa != coda) {
agg = testa.struttura.frequenza + testa.succ.struttura.frequenza;
for (t = coda; t != null && t.struttura.frequenza > agg; t = t.prec);
y = new NodoP(t,t.succ);
t.succ = y;
if (t == coda) coda = y;
else y.succ.prec = y;
y.struttura = new Nodo((byte)0,agg,0,testa.struttura,testa.succ.struttura);
testa = testa.succ.succ;
testa.prec = null;
}

in pratica a ogni iterazione toglie 2 nodi raggruppandoli in un minialbero la cui radice viene concatenata nella lista. quindi con N elementi devo iterare N-1 volte credo.... :confused:
Il ciclo for interno fa ogni volta una ricerca partendo dall'ultimo nodo della lista e andando all'indietro. In teoria considerando il caso peggiore il suo costo è n?
Quindi il totale sarebbe O(N-1)*(N + spiccioli) cioè anche qui O(N^2)?

La trasforma dovrebbe eseguire tutte le sue operazioni solo per i nodi terminali, diciamo N; mentre per gli altri chiama la ricorsione e in teoria dovrebbero essere N-1 quindi non so se è O(N^2) oppure O(N+(N-1))=O(2N)=O(N)

????

Grazie ancora a tutti :ave: