PDA

Visualizza la versione completa : [?] Complessità algoritmica


pax22
19-05-2008, 11:18
Dunque, chiarito l'arcano, vorrei aprire una discussione sulla complessità (Lìeventualità di avere un tool o comunque di effettuare una ricerca per trovarlo era solamente una richiesta aggiuntiva...).
Io ho 3 for in cascata dove, nel secondo, c'è anche una chiamata ricorsiva.

Poichè i 3 for sono così strutturati :

for i:=0 until N do
for j:=0 until M do
for k:=0 until P do{....
}
return inv(i,j);
}
}

Io ho pensato che la complessità potesse venire espressa come O(NMP) e quindi possa crescere polinomialmente con N,M,P...Il problema è che la ricorsione mi dà un upper bound maggiore che è esponenziale...quindi direi O(2^NM)....
Come fare ad unire questi due pezzi...

Scusate,probabilmente la domanda non è di natura di programmazione,però onestamente ho preferito inserirla qui perchè credo che molte persone che hanno programmato seriamente, almeno una volta, si sono chieste quanto è la complessità spaziale e temporale della loro applicazione...Perchè penso, che un giorno, ci paghino anche per questo....
E anche se questo esula dalle prerogative del topic, credo sia molto più importante di riuscire a mettere insieme due for e un if,che prima o poi potrebbero riuscire a fare tutti....scusate è un IMHO...

Loading