La Notazione O-Grande¶

Cercando di caratterizzare l’efficienza di un algoritmo in termini di tempo di esecuzione indipendentemente dall’implementazione, dal linguaggio o dal computer, è importante quantificare il numero di operazioni o passi che l’algoritmo richiederà.

In questo contesto, il tempo di esecuzione di un algoritmo corrisponde al numero di passi cha esegue, dove ogni passo costa tempo unitario. Per esempio, una definizione di passo algoritmico nella funzione sumOfN potrebbe essere il numero di istruzioni di assegnamento. Tale numero è 1 (\(theSum = 0\)) più il valore di n (il numero di volte che facciamo \(theSum=theSum+i\)). Possiamo denotare questa funzione come T, dove \(T(n)=1 + n\). Il parametro n corrisponde alla “grandezza dell’input,” o “taglia del problema,” e possiamo leggerlo come “T(n) è il tempo che serve per risolvere un problema di taglia n, ovvero 1+n passi.”

Tuttavia, il numero esatto di operazioni non è importante, quanto invece lo è l’ordine di grandezza. A tale ordine di grandezza partecipano per lo più le parti dominanti dell’algoritmo, le più costose, in quanto quando n cresce, la parte più pesante dell’algoritmo pesa molto di più rispetto alle altre. In altre parole, quando n cresce, la parte più dominante di \(T(n)\) tende a sovrastare gli altri termini. Questa parte dominante è ciò che ci interessa per confrontare algoritmi.

La funzione ordine di grandezza descrive la parte dominante di \(T(n)\) che è la parte che si incrementa più velocemente al crescere di n. L’ordine di grandezza è spesso chiamata O-grande e viene scritto come \(O(f(n))\), fornendo un’approssimazione utile al numero di passi della computazione. La funzione \(f(n)\) fornisce una semplice rappresentazione della parte dominante di \(T(n)\).

Nell’esempio sopra, \(T(n)=1+n\). Quando n diventa grande, la costante 1 non è più importante in quanto dominata dal termine più significativo n. Per cui diciamo che il tempo è \(O(n)\).

Se abbiamo un numero di passi pari a \(T(n)=5n^{2}+27n+1005\). Quando n è piccolo, la costante 1005 sembra dominare. Tuttavia, quando n diventa grande il termine \(n^{2}\) diventa il più importante. Dunque la funzione \(T(n)\) ha ordine di grandezza \(f(n)=n^{2}\), o che semplicemente è \(O(n^{2})\).

Spesso, il comportamento dell’algoritmo dipende dal valore esatto dei dati e non solo da quanti sono. In questo caso, ci sono diverse misure che potremmo considerare:

• caso peggiore, quanto ci mette nel caso in cui gli n dati siano quelli per cui l’algoritmo si comporta peggio?
• caso medio, quanto ci mette in media considerando tutti i possibili insiemi di n dati.

Gli ordini di grandezza più comuni sono mostrati in Table 1. Per capire quali di queste funzioni dominino una sull’altra, dobbiamo analizzare il loro comportamento quando n è grande.

Figura 1 mostra il grafico delle funzioni di Tabella 1. Quando n è piccolo la gerarchia non è ben definita, mentre quando n cresce è chiaro quale funzione domina sull’altra.

Figura 1: Grafico delle funzioni più comuni O-Grande

Come esempio finale, supponiamo di avere il frammento in Listing 2. Sebbene questo programma non faccia niente, possiamo analizzarne le performance.

Listing 2

a=5
b=6
c=10
for i in range(n):
   for j in range(n):
      x = i * i
      y = j * j
      z = i * j
for k in range(n):
   w = a*k + 45
   v = b*b
d = 33

E’ facile vedere che il numero di assegnamenti è \(O(n^{2})\) per i primi due for (di cui uno annidato) e \(O(n)\) per il for su k. Dal momento che \(O(n^{2}) + O(n) = O(n^{2})\), ovvero la parte dominante è \(O(n^{2})\), il costo dell’algoritmo è \(O(n^{2})\) quando n cresce.

Figura 2: Confrontanto \(T(n)\) con funzioni O-grande comuni

Figura 2 mostra alcune delle funzioni comuni di O-grande e come si confrontano con la funzione \(T(n)\) discussa sopra. Notiamo che \(T(n)\) all’inizio è più grande della funzione cubica. Tuttavia, quando n cresce, la funzione cubica sovrasta \(T(n)\).