Lezione del 13 marzo 2009
Abbiamo visto che, dato un numero naturale m, se rappresentiamo m inbase 2 : m = ak-12k-1+ak-22k-2+…+a121+a020 (dove ai sono le cifre binarie =0,1)
e se supponiamo che non vi siano cifre nulle (non significative) fra quelle più a sinistra (cioè in pratica se ak-1=1), il numero k=L(m) di cifre della rappresentazione binaria di m è detto lunghezza (binaria) di m.
Essendo la quantità ak-22k-2+…+a121+a020 non negativa, si ha m ak-12k-1 =2k-1. D’altronde ai 1 per ogni i,dunque:
m 2k-1+2k-2+…+21+20 = (2k-1)/(2-1) = 2k-1 < 2k
(dove si è sfruttata l’identità algebrica xk-1+xk-2+…+x1+x0 = (xk-1)/(x-1)).
In totale, se k=L(m), si ha:
2k-1≤m<2k
Dunque, calcolando il logaritmo in base 2:
k-1≤log2m<k
ossia k-1=log2m (dove in generale, dato un numero reale x, indichiamo con x la cosiddetta parte intera di x, ossia il massimo intero che sia x). Da ciò si ricava la formula per il calcolo della lunghezza di m:
k=L(m)=log2m+1.
Chiameremo dimensione dell’input (di un algoritmo) la lunghezza binaria dell’input stesso (se l’input è costituito da più numeri naturali, sceglieremo la lunghezza massima di tali numeri come valore della dimensione dell’input).
Dato un algoritmo A potremmo allora definire il valore TimeA(n) come il numero di operazioni elementari eseguite nell’algoritmo quando l’input ha dimensione n: tale definizione non sarebbe però univoca perché due diversi input di eguale dimensione n potrebbero dar luogo a un diverso numero di operazioni elementari nell’esecuzione dell’algoritmo.
Definiremo allora il valore TimeA(n) come il numero di operazioni elementari eseguite nell’algoritmo quando l’input ha dimensione n nel caso peggiore (cioè quello in cui il numero di operazioni elementari è il massimo, fra tutti i casi in cui l’input ha dimensione n).
Spesso però, nei casi concreti non interessa (e non è facile) calcolare il valore esatto di TimeA(n) ma piuttosto studiare quanto velocemente cresce il valore di TimeA(n) al crescere della dimensione n dell’input, e a tale scopo possiamo servirci della teoria della “big-O”.
La relazione “big-O”.
La notazione “big-O” fu introdotta da Bachmann e resa popolare da Landau.
Siano N l’insieme dei numeri naturali (cioè degli interi positivi) ed R+ l’insieme dei numeri reali positivi.
Date due funzioni f,g: N R+ diremo che f è di ordine g e scriveremo f(n)=O(g(n)) o semplicemente f=O(g) se esiste una costante reale C tale che per ogni nN si abbia f(n)≤Cg(n) (notare che necessariamente C>0).
La definizione precedente equivale a dire che esiste una costante reale C tale che f(n)/g(n)≤C, ossia:
f=O(g) la funzione rapporto f/g è limitata superiormente.
In pratica, se f=O(g), possiamo affermare che, al crescere dell’argomento nN, i valori f(n) crescono in percentuale non più velocemente dei valori g(n): infatti se m,nN e se m>n si ha f(m)/f(n)≤(Cg(m))/(Cg(n))=g(m)/g(n). Per esempio se g(n)=n2 e se f=O(g), si ha
f(2n)/f(n)≤(2n)2/n2=4, ossia al raddoppiare dell’argomento n, il valore f(n) non aumenta più del quadruplo (ossia non aumenta più di quanto aumenti la funzione n2 al raddoppiare di n).
La f=O(g) non deve quindi essere intesa come una eguaglianza ma come una relazione (simile alla relazione ≤) fra funzioni con dominio N e codominio R+: in particolare essa soddisfa banalmente la proprietà riflessiva f=O(f) (essendo f(n)≤f(n)), e la proprietà transitiva (se f=O(g), e se g=O(h), allora f(n)≤Cg(n), g(n)≤Dh(n) con C,D costanti, da cui f(n)≤CDh(n) ossia f=O(h)) ma non sempre la proprietà simmetrica. Infatti se f=O(g) non è detto che sia anche g=O(f) (come si vede dalle considerazioni che seguono).
Alcune osservazioni utili:
- se limnf(n)/g(n)=, allora certamente la funzione f/g non è limitata superiormente quindi non è vero che f=O(g),
- se limnf(n)/g(n)=k< allora è noto che la funzione f/g è limitata, dunque f=O(g)
- in particolare se limnf(n)/g(n)=k< con k0 allora f=O(g) ma anche g=O(f) perché limng(n)/f(n)=1/k<; ma se limnf(n)/g(n)=0 allora f=O(g), ma non è vero che g=O(f) perché limng(n)/f(n)=.
L’ultima osservazione fornisce facili esempi di funzioni f,g tali che f=O(g) ma non g=O(f): basta che sia limnf(n)/g(n)=0 (per esempio n=O(n2) ma non è vero che n2=O(n)).
Quando è vero che f=O(g) ma non è vero che g=O(f), si ha in pratica una relazione di < “stretto” fra la velocità di crescita di f e quella di g.
Ovviamente, per avere una “misura” della velocità di crescita della funzione f, si può cercare una funzione “conosciuta” g tale che f=O(g): esempi molto comuni di g sono le funzioni polinomiali, logaritmiche, esponenziali etc…
Data una funzione polinomiale g(n)=a0+a1n+a2n2+….+aknk (dove ai sono costanti reali 0 non tutte nulle e il grado k è un intero fissato 0), si ha ni≤nk ed per ogni i=0,1,…,k ed ogni naturale n, dunque f(n)≤ a0nk+a1nk+a2nk+….+aknk=Cnk, dove C=ao+…+ak, e si conclude che g=O(nk).
Una funzione f: N R+ è detta di ordine polinomiale se esiste una funzione polinomiale g tale che f=O(g): per quanto precede ciò equivale a dire che f=O(nk) per un opportuno k intero 0.
In particolare se f=O(n) diremo che f è di ordine lineare, se f=O(n2) diremo che f è di ordine quadratico e così via.
Diremo che una funzione f: N R+ è di ordine esponenziale se f=O(an) per un’opportuna costante reale a>1.
Diremo che una funzione f: N R+ è di ordine logaritmico se f=O(logan) per un opportuna costante reale a>1.
Notiamo che, fissati a,b reali >1 per ogni numero naturale n si ha logbn=logbalogan, dunque (essendo logba costante) si conclude che logbn=O(logan) quindi tutte le funzioni logaritmiche hanno lo stesso ordine, indipendentemente dalla base.
Invece, per le funzioni polinomiali, fissati 2 esponenti h,k interi 0 con h<k, essendo limnnh/nk= limn1/nk-h=0 si ha nh=O(nk) ma non nk=O(nh).
In termini di velocità di crescita al crescere di n, possiamo elencare in ordine “strettamente crescente” alcune delle funzioni più comuni (dove a>1 è un numero reale fissato):
logan<n<n2<n3<………<nk<……..<an
dove il segno < è puramente convenzionale ed è giustificato dal fatto che il limite del rapporto di ognuna delle funzioni rispetto alla successiva dell’elenco è 0 (semplice esercizio di analisi).
Complessità computazionale di un algoritmo
Tornando alla nostra definizione di TimeA(n), valore che indica il numero di operazioni elementari eseguite (nel caso peggiore) dall’algoritmo A su un input di dimensione n, possiamo considerare TimeA(n) come funzione della dimensione n e stimare la sua velocità di crescita trovando opportune funzioni g(n) tali che TimeA(n)=O(g(n)): diremo in tal caso che l’algoritmo A ha complessità computazionale O(g).
In particolare diremo che l’algoritmo A ha complessità computazionale polinomiale se la funzione TimeA(n) è di ordine polinomiale, e che l’algoritmo A ha complessità computazionale esponenziale se la funzione TimeA(n) è di ordine esponenziale: nel primo caso f=O(nk) per un opportuno k intero 0, nel secondo f=O(an) per un’opportuna costante reale a>1.
Gli algoritmi di complessità polinomiale sono considerati più efficienti di quelli di complessità esponenziale, perché, al crescere della lunghezza n dell’input, il tempo di esecuzione nei primi cresce molto meno velocemente che nei secondi.
Tuttavia, per un fissato valore della lunghezza n dell’input, un algoritmo di complessità polinomiale può avere un tempo di esecuzione più alto di un algoritmo di complessità esponenziale.
Esempio: Siano dati l’algoritmo A con TimeA(n)=n7 di complessità polinomiale e l’algoritmo B con TimeA(n)=2n di complessità esponenziale. Per un input di lunghezza n=32 (quindi un input con 32 cifre binarie) l’algoritmo A esegue un massimo di 327=235 operazioni, mentre l’algoritmo B esegue un massimo di 232 (quindi un numero inferiore): se ogni operazione è eseguita in 1 milionesimo di secondo, l’algoritmo A impiega un massimo di circa 9 ore e mezza, l’algoritmo B un massimo di circa 1 ora e 12 minuti. Ma per un input di lunghezza doppia n=64 l’algoritmo A esegue un massimo di 647 operazioni (circa 52 giorni), ma l’algoritmo B un massimo di 264 operazioni (circa 585.00 anni !!!).
E’ anche vero che un algoritmo di complessità polinomiale può essere egualmente “intrattabile” ed avere tempi di esecuzione molto alti: se per esempio Time(n)=Cnk (con C costante) allora Time(n)=O(nk) ha complessità polinomiale, ma se la costante C è per esempio C=1010000 oppure l’esponente k è k=10000, il numero di operazioni elementari eseguite dall’algoritmo è
“astronomico” anche per input di dimensione non molto grande.
