Teoria dei numeri e Crittografia: lezione del 23 marzo 2011
Un criterio per confrontare gli ordini delle funzioni f, g è quello di studiare il limite del rapporto f(x)/g(x) per x.
1) Se tale limite esiste finito è noto (da risultati di Analisi) che il rapporto f(x)/g(x) è limitato, dunque g domina f ed O(f)O(g).
2) Se tale limite esiste ed è , allora g non domina f , perché è noto (sempre da risultati di Analisi) che in questo caso il rapporto f(x)/g(x) è illimitato.
3) Da 1) e 2) segue anche che se tale limite esiste finito ed è non nullo allora O(f)=O(g): infatti detto l il limite, si ha che il limite del rapporto g(x)/f(x) per x è l-1<, e basta applicare la proprietà 1) per ottenere che f, g si dominano reciprocamente. Se invece tale limite esiste finito ed è =0 allora O(f)<O(g): infatti per la 1) g domina f , ma per la 2) f non domina g essendo il limite del rapporto g(x)/f(x) per x.
4) Se tale limite non esiste, niente si può dire, se non con ulteriori considerazioni, sugli ordini di f, g (che potrebbero anche non essere confrontabili).
Esempi.
1) Date le funzioni f , g definite rispettivamente da:
f(x)=1 per x dispari, f(x)=x per x pari g(x)=x per x dispari, g(x)=1 per x pari
non esiste il limite del rapporto f(x)/g(x) per x, in quanto f(x)/g(x)=1/x per x dispari, f(x)/g(x)=x per x pari. Poiché il rapporto f(x)/g(x) è illimitato si deduce che g non domina f, ma poiché anche il rapporto g(x)/f(x) è illimitato (perché g(x)/f(x)=x per x dispari e g(x)/f(x)=1/x per x pari) si deduce che neanche f domina g : dunque gli ordini di f e g non sono confrontabili.
2) Date le funzioni f , g definite rispettivamente da:
f(x)=1/x per x dispari, f(x)=x per x pari g(x)=2/x per x dispari, g(x)=x2 per x pari
non esiste il limite del rapporto f(x)/g(x) per x, in quanto f(x)/g(x)=1/2 per x dispari, f(x)/g(x)=1/x per x pari. Poiché però il rapporto f(x)/g(x) è limitato si deduce che g domina f, ma poiché invece il rapporto g(x)/f(x) è illimitato (perché g(x)/f(x)=2 per x dispari e g(x)/f(x)=x per x pari) si deduce che f non domina g : dunque O(f)<O(g).
Per valutare l’ordine di una funzione f si considerano delle opportune funzioni g di riferimento con cui confrontare l’ordine di f, ottenendo vari “tipi” di ordine.
La funzione f ha ordine polinomiale di grado n (dove n è un intero non negativo) se O(f)=O(g) dove g è una funzione polinomiale di grado n della forma:
g(x) = a0+a1x+……+anxn con i coefficienti ai reali, e con an≠0.
Si noti che in tale caso si ha O(a0+a1x+……+anxn )= O(xn) perché il limite del rapporto:
( a0+a1x+……+anxn)/xn per x è an≠0.
Dunque la funzione f ha ordine polinomiale di grado n se O(f)=O(xn).
Nel caso n=0 si ha: O(f)=O(1) se e solo se la funzione f(x) è limitata.
In particolare per n=1,2 si ottengono le funzioni di ordine lineare e quadratico rispettivamente.
Più in generale è interessante studiare tutte le funzioni del tipo f(x)=xt dove t è un esponente reale non negativo (non necessariamente intero): un esempio é f(x)=x1/2=x.
Per queste funzioni notiamo che al crescere dell’esponente t cresce strettamente l’ordine della funzione xt: se 0≤t<s l’ordine di xtè strettamente minore di quello di xs perché è 0 il limite del rapporto xt/xs=xt-s per x (essendo t-s<0).
Inoltre una funzione della forma xt con t non intero ha ordine strettamente compreso fra quello di 2 funzioni polinomiali: se infatti poniamo m=t (parte intera di t), da m<t<m+1 si ha:
O(xm) < O(xt) <O(xm+1)
La funzione f ha ordine logaritmico se O(f)=O(g) dove g è una funzione logaritmica della forma g(x) = loga(x) per una opportuna base reale a>1.
Notiamo che tutte le funzioni logaritmiche hanno lo stesso ordine, indipendentemente dalla base scelta: infatti se a,b>1 sono due basi, dalla formula loga(x) = loga(b)logb(x) segue che il rapporto loga(x) / logb(x)= loga(b) è costante dunque O(loga(x))= O(logb(x)) .
Notiamo anche che O(1)<O(loga(x))<O(x) perché per x si ha lim 1/ loga(x) = lim loga(x)/x = 0.
La funzione f ha ordine esponenziale se O(f)=O(g) dove g è una funzione esponenziale della forma g(x) = ax per una opportuna base reale a>1.
Notiamo che al crescere della base a cresce strettamente l’ordine della funzione esponenziale ax : se 1<a<b l’ordine di axè strettamente minore di quello di bx perché 0= lim ax/bx =lim (a/b)x per x
(essendo a/b<1).
Se a>1 ponendo k=logea>0 si ha ax=ekx dunque si può dire che la funzione f ha ordine esponenziale se O(f)=O(ekx) per una opportuna costante reale k>0 .
Una qualunque funzione di ordine polinomiale O(xn) (con n intero non negativo) è sempre di ordine strettamente minore di qualunque funzione di ordine esponenziale O(ekx) (con k>0): infatti applicando n volte la regola di de l'Hôpital si ottiene che il limite (per x) del rapporto xn/ekx coincide con il limite del rapporto (n!)/(knekx) che è 0.
Una funzione ha ordine superpolinomiale se ha ordine strettamente maggiore di qualunque funzione polinomiale (per esempio se ha ordine esponenziale) ed ha ordine subesponenziale se ha ordine strettamente minore di qualunque funzione esponenziale (per esempio se ha ordine polinomiale).
Esistono funzioni che sono di ordine sia superpolinomiale che subesponenziale (quindi di ordine strettamente compreso fra il polinomiale e l’esponenziale): per esempio la funzione e(x/logx).
Si può infatti dimostrare, con gli usuali metodi analitici, che il limite dei rapporti:
xt/e(x/logx) e(x/logx)/ax è 0, per x .
Esistono anche funzioni di ordine strettamente maggiore dell’ordine esponenziale: in un esempio nella lezione precedente si è dimostrato che la funzione esponenziale f(x)=ax (per ogni base reale a>1) è dominata dalla funzione “fattoriale” g(x)=x! . D’altronde, con metodi analoghi a quelli dell’esempio citato, si può verificare che il rapporto x!/ax è illimitato, dunque g non è dominata da f, e si conclude che O(ax)<O(x!).
Compatibilità della relazione di dominazione con le operazioni fra funzioni.
Notiamo prima di tutto che se f è una funzione e se k>0 è una costante reale, posto g=kf (nel senso che g(x)=kf(x) per ogni x) si ha ovviamente O(f)=O(g), essendo costante il rapporto f/g .
La relazione di dominazione è “compatibile” con la somma e il prodotto di funzioni: se O(f1)O(g1), O(f2)O(g2) allora O(f1f2)O(g1g2) ed O(f1+f2)O(g1+g2), dove il prodotto delle funzioni f,g è definito da (fg)(x)=f(x)g(x) e la somma da (f+g)(x)=f(x)+g(x)).
Infatti se esistono costanti k, m tali che f1(x)kg1(x), f2(x)mg2(x) allora (f1f2)(x)=f1(x)f2(x)kmg1(x)g2(x)=km(g1g2)(x)
(f1 +f2)(x)=f1(x)+f2(x)h(g1(x)+g2(x))=h(g1 +g2)(x) dove h=max{k, m}.
Da questi risultati ovviamente segue che se O(f1)=O(g1), O(f2)=O(g2) allora:
O(f1f2)=O(g1g2) ed O(f1 +f2)=O(g1 +g2).
In particolare se O(f1)O(f), O(f2)O(f) allora O(f1+f2)O(2f)=O(f).
Notiamo inoltre che si ha:
O(f) O(f+g)
per ogni coppia di funzioni f, g (perché f(x)<f(x)+g(x) essendo le funzioni a valori positivi, dunque f+g domina f ).
Inoltre:
O(f)O(g) O(f+g)=O(g)
Infatti se O(f)O(g) allora, essendo O(g)O(g), si ha O(f+g) O(g+g)=O(2g)=O(g), dunque O(f+g)=O(g) (perché O(f) O(f+g) è in ogni caso vero).
Viceversa se O(f+g)=O(g), allora O(f) O(f+g)=O(g).
L’ultimo risultato dimostra che nella somma di funzioni “prevale” quella di ordine maggiore (se gli ordini delle 2 funzioni sono confrontabili): se per esempio f ha ordine polinomiale e g ordine esponenziale, la somma f+g avrà ordine esponenziale.
La compatibilità della relazione di dominazione con il prodotto di funzioni implica invece che il prodotto di funzioni di ordine polinomiale (risp. esponenziale) è di ordine polinomiale (risp.
esponenziale): infatti se O(f)=O(xn), O(g)=O(xm) allora O(fg)=O(xnxm)=O(xn+m); se invece O(f)=O(ekx), O(g)=O(ehx) (con k,h>0) allora O(fg)=O(ekxehx)=O(e(k+h)x).
Il prodotto di una funzione di ordine polinomiale per una di ordine esponenziale ha ordine strettamente maggiore di quello del fattore di ordine esponenziale (e per transitività anche di quella di ordine polinomiale): se O(f)=O(xt), O(f)=O(ekx) (con k>0), allora O(fg)<O(ekx), in quanto per x si ha lim[xt/(xtekx)]=lim(1/ekx)=0 .
