Stime asintotiche negli algoritmi...

[idinweb]

se eseguo n volte un ciclo la complessità è O(n), se eseguo n volte un ciclo
che esegue a sua volta un ciclo avro O(n^2) ma se eseguo un ciclo n volte e
richiamo m volte un altro ciclo la complessità è O(m*n)? o in informatica la
stima asintotica mi porta comunque ad o(n^2)?

[Kiuhnm]

Post by idinweb
se eseguo n volte un ciclo la complessità è O(n), se eseguo n volte un ciclo
che esegue a sua volta un ciclo avro O(n^2) ma se eseguo un ciclo n volte e
richiamo m volte un altro ciclo la complessità è O(m*n)? o in informatica la
stima asintotica mi porta comunque ad o(n^2)?

No, sono due cose diverse. Solitamente m può essere riscritto in
funzione di n. Se è invece un parametro indipendente, l'analisi si
complica. Non avrai più T(n), ma T(n,m). Nota comunque che potrebbe
essere conveniente esprimere la "dimensione" del problema in un modo
tale da esprimere sia n che m come unico parametro. La dimensione del
problema potrebbe essere per es. la lunghezza di una stringa che lo
definisce. Ma questo complica ulteriormente le cose ed è accettabile
soltanto nel caso siano sufficienti stime piuttosto approssimative (per
es. in relazione a P vs NP\P).

Kiuhnm