Lezione del 5 marzo 2007
Spesso però nei casi concreti non interessa 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.
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 f=O(g): infatti, fissato a piacere un reale >0, esiste un n0N tale che f(n)/g(n)<k+ per ogni n>n0, e se C=max{f(1)/g(1),…,f(n0)/g(n0),k+} si ha f(n)/g(n)≤C per ogni nN
- 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 crescita di f e quella di g.
Vediamo alcune proprietà elementari della relazione “big-O”:
1) data la funzione f: N R+ , dire che f=O(1) (cioè che f è di ordine g dove g(n)=1 per ogni nN) equivale a dire che esiste una costante C tale che f(n)≤C, dunque che f è limitata superiormente 2) data la funzione f: N R+ e se k è una costante reale >0, si può definire la funzione kf: N R+ ponendo (kf)(n)=kf(n): si ha allora f=O(kf) e kf=O(f) (perché limnf(n)/kf(n)=1/ k<)
3) se f,g: N R+ sono funzioni, si possono definire le funzioni somma e prodotto f+g, fg: N R+ ponendo (f+g)(n)=f(n)+g(n), (fg)(n)=f(n)g(n); se allora f,g,h,t: N R+ sono funzioni e se f=O(h),
g=O(t) si ha f+g=O(h+t), fg=O(ht) (perché se f(n)≤Ch(n), g(n)≤Dt(n), con C,D costanti, si ha f(n) +g(n) )≤S(h(n)+t(n)) dove S=max{C,D}, e inoltre f(n)g(n)≤CDh(n)t(n))
4) caso particolare di 3): se f=O(h) e g=O(h) allora f+g=O(2h) quindi f+g=O(h) (per la 2))
5) fissati a,b reali >1 (in modo che le funzioni f(n)=logan>0, g(n)=logbn siano funzioni N R+), 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
6) se f: N R+ è tale che limnf(n)=, e se k è una costante reale tale che la funzione somma k+f abbia valori positivi (per es. se k>0 o più in generale se k>-f(n) per ogni n), allora si ha f=O(k+f) ed anche k+f=O(f) (perché limn[k+f(n)]/f(n)=1).
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, e il grado k è un intero fissato 0), si ha ni≤nk per ogni i=0,1,…,k, dunque aini≤aini≤aink per ogni i=0,1,
…,k, da cui f(n)≤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.
Una funzione f di ordine non polinomiale (cioè tale che non si abbia f=O(nk) per nessun intero k0) è detta di ordine superpolinomiale.
Fra le funzioni di ordine superpolinomiale, particolarmente interessanti sono quelle di ordine esponenziale: diremo che una funzione superpolinomiale f: N R+ è di ordine esponenziale se f=O(an) per un’opportuna costante reale a>1.
