Informatica I - l'andamento asintotico delle prestazioni di un algoritmo

Analisi delle prestazioni di un algoritmo

Teniamo presente che, nell’analisi delle prestazioni di un algoritmo, ci interessano le prestazioni asintotiche per valori elevati di n (andamento asintotico).

Esempio

Se n vale 1000, allora:

• 1/2*n vale 500, circa 1% del totale
• 9/2*n - 5 vale 4495

Quindi diciamo che l'andamento asintotico dell’algoritmo in funzione di n è:

Facciamo un’ulteriore semplificazione. Ci interessa soltanto valutare cosa succede al tempo d’esecuzione T(n) se n, ad esempio, raddoppia o quadruplica. Nel caso in esame:

Il tempo di esecuzione T(2n) è:

• 2T(n) = 2 * 2 * (2) = 4*T(n)

Si osserva che T(2n) = 4*T(n). Questo è vero in generale nel caso in cui sia presente un fattore moltiplicativo, indipendentemente dal fatto che sia 1/2 o qualsiasi altro fattore moltiplicativo c.

Notazione "O-grande"

Si dice quindi che per ordinare un array con l’algoritmo di selezione si effettua un numero di accessi che è dell’ordine di n². Per esprimere sinteticamente questo concetto si usa la notazione O-grande e si dice che il numero degli accessi è O(n²).

Dopo aver ottenuto una formula che esprime l’andamento temporale dell’algoritmo, si ottiene la notazione “O-grande” considerando soltanto il termine che si incrementa più rapidamente all’aumentare di n, ignorando coefficienti costanti.

La notazione f(n) = O(g(n)) significa che f non cresce più velocemente di g. Ma è possibile che f cresca molto più lentamente (Esempio: f(n) = n + 5n – 3 è O(n³), ma è anche O(n¹⁰)).

Ulteriori notazioni

• f(n) = Ω(g(n)) significa che f non cresce più lentamente di g, ovvero g(n) = O(f(n)).
• f(n) = Θ(g(n)) significa che f cresce con la stessa velocità di g, ovvero f(n) = O(g(n)) e f(n) = Ω(g(n)).

Esiste una costante C > 0 tale che:

• f(n) = O(g(n)) ↔ f(n)/g(n) < C definitivamente
• f(n) = Ω(g(n)) ↔ f(n)/g(n) > C definitivamente
• f(n) = Θ(g(n)) ↔ C < f(n)/g(n) < C definitivamente