Notazione asintotica

In questa pagina 7

Si considerano funzioni $f, g : \mathbb{N} \to \mathbb{R}$ positive per $n$ abbastanza grande. L'analisi asintotica ignora i fattori moltiplicativi costanti e i termini additivi non dominanti (vedi Complessità in tempo e caso pessimo). È lo stesso ragionamento del confronto tra infiniti in Analisi 1 (Limiti di successioni, Asintoticità e o-piccolo, Limiti notevoli e gerarchia degli infiniti): la differenza è che qui si lavora con disuguaglianze e costanti esplicite invece che con limiti, e il simbolo $o$ ha lo stesso significato "strettamente trascurabile" ( $f/g \to 0$ ).

Le quattro definizioni

Definizione (notazioni $O$ , $\Omega$ , $\Theta$ e $o$ )

Notazione Definizione Si legge

$f \in O(g)$ $\exists\, c > 0,\ n_0 \ge 1$ : $f(n) \le c\,g(n)$ per ogni $n \ge n_0$ $f$ cresce al più come $g$

$f \in \Omega(g)$ $\exists\, c > 0,\ n_0 \ge 1$ : $f(n) \ge c\,g(n)$ per ogni $n \ge n_0$ almeno come $g$

$f \in \Theta(g)$ $f \in O(g)$ e $f \in \Omega(g)$ , cioè $c' g \le f \le c'' g$ definitivamente come $g$

$f \in o(g)$ $\forall\, c > 0\ \exists\, n_0$ : $f(n) \le c\,g(n)$ per $n \ge n_0$ ; equivale a $\lim f/g = 0$ strettamente meno di $g$

Notazione	Definizione	Si legge
$f \in O(g)$	$\exists\, c > 0,\ n_0 \ge 1$ : $f(n) \le c\,g(n)$ per ogni $n \ge n_0$	$f$ cresce al più come $g$
$f \in \Omega(g)$	$\exists\, c > 0,\ n_0 \ge 1$ : $f(n) \ge c\,g(n)$ per ogni $n \ge n_0$	almeno come $g$
$f \in \Theta(g)$	$f \in O(g)$ e $f \in \Omega(g)$ , cioè $c' g \le f \le c'' g$ definitivamente	come $g$
$f \in o(g)$	$\forall\, c > 0\ \exists\, n_0$ : $f(n) \le c\,g(n)$ per $n \ge n_0$ ; equivale a $\lim f/g = 0$	strettamente meno di $g$

Esempio. $3n+4\in O(n)$ con $c=4$ e $n_0=4$ , perché $3n+4\le4n\iff n\ge4$ (si porta $3n$ a destra: $4 \le n$ ).

Per vederlo, il grafico mostra $3n+4$ sotto $4n$ dal punto $n_0=4$ in poi: prima i due andamenti si incrociano, ma ciò che conta è che da $n_0$ in avanti la disuguaglianza resta vera per sempre.

Grafico interattivo: 3n+4 è O(n): con c = 4 la retta 4n sta sopra 3n+4 da n0 = 4 in poi (in n = 4 valgono entrambe 16)

Le costanti $c$ ed $n_0$ non dipendono da $n$ . Per $o$ vale invece "per ogni $c$ ", e $n_0$ dipende da $c$ .

Esempi con le costanti

$3n + 4 \in O(n)$ con $c = 7$ , $n_0 = 1$ : per $n \ge 1$ vale $4 \le 4n$ , quindi $3n + 4 \le 3n + 4n = 7n$ . Anche con $c = 4$ e $n_0 = 4$ : $3n + 4 \le 4n \iff n \ge 4$ .
$n + 2n^2 \in O(n^2)$ con $c = 3$ , $n_0 = 1$ : per $n \ge 1$ si ha $n \le n^2$ (moltiplicando $1 \le n$ per $n>0$ ), quindi $n + 2n^2 \le n^2 + 2n^2 = 3n^2$ .
$3n + 4 \in O(n^2)$ con $c = 4$ , $n_0 = 4$ : per $n \ge 4$ vale $3n + 4 \le 4n$ (sopra) e $4n \le 4n^2$ perché $n \le n^2$ . Vero ma poco informativo: non è un limite stretto.
$2^{100} \in O(1)$ con $c = 2^{100}$ : una costante è limitata da se stessa per ogni $n$ .
$3n + 4 \in \Omega(n)$ con $c = 3$ : $3n + 4 \ge 3n$ perché $4 > 0$ . $6n^2 + 1 \in \Omega(n)$ con $c = 6$ : $6n^2 + 1 \ge 6n^2 \ge 6n$ per $n \ge 1$ .
$100 n \in o(n^2)$ : dato qualsiasi $c>0$ , $100 n \le c\,n^2 \iff 100 \le c\,n \iff n \ge 100/c$ (si divide per $n>0$ ); si prende $n_0 = \lceil 100/c \rceil$ . Qui $n_0$ dipende da $c$ , come richiesto da $o$ .
$3n/\log_2 n \in o(n)$ perché il rapporto $\dfrac{3n/\log_2 n}{n} = \dfrac{3}{\log_2 n} \to 0$ (limite di successione: Limiti di successioni).

Proprietà

Polinomi: $\sum_{i=0}^{k} a_i n^i \in \Theta(n^k)$ $\sum_{i = 0}^{k} a_{i} n^{i} \in Θ (n^{k})$ se $a_k > 0$ $a_{k} > 0$ e $k, a_i$ $k, a_{i}$ costanti. Per $O$ $O$ si prende $c = \sum |a_i|$ $c = \sum ∣ a_{i} ∣$ , $n_0 = 1$ $n_{0} = 1$ . Per $\Omega$ $Ω$ si pone $\gamma = \max_{i<k}|a_i|$ $γ = max_{i < k} ∣ a_{i} ∣$ e si usa che $\sum_{i<k} a_i n^i \ge -k\gamma n^{k-1}$ $\sum_{i < k} a_{i} n^{i} \geq - kγ n^{k - 1}$ , da cui per $n \ge 2k\gamma/a_k$ $n \geq 2 kγ / a_{k}$ si ottiene $\ge \frac{a_k}{2} n^k$ $\geq \frac{a _{k}}{2} n^{k}$ . Passaggi: per $n \ge 1$ $n \geq 1$ ciascuno dei $k$ $k$ termini $a_i n^i$ $a_{i} n^{i}$ con $i<k$ $i < k$ vale in modulo al più $\gamma n^{i} \le \gamma n^{k-1}$ $γ n^{i} \leq γ n^{k - 1}$ , quindi la loro somma non scende sotto $-k\gamma n^{k-1}$ $- kγ n^{k - 1}$ . Allora $f(n) \ge a_k n^k - k\gamma n^{k-1} = n^{k-1}\,(a_k n - k\gamma),$ e se $n \ge 2k\gamma/a_k$ $n \geq 2 kγ / a_{k}$ si ha $k\gamma \le \frac{a_k n}{2}$ $kγ \leq \frac{a _{k} n}{2}$ , cioè $a_k n - k\gamma \ge \frac{a_k n}{2}$ $a_{k} n - kγ \geq \frac{a _{k} n}{2}$ , da cui $f(n) \ge \frac{a_k}{2} n^k$ $f (n) \geq \frac{a _{k}}{2} n^{k}$ . Esempio: $(n+1)^5 \in \Theta(n^5)$ $(n + 1)^{5} \in Θ (n^{5})$ , perché sviluppando con il Binomio di Newton si ottiene un polinomio di grado $5$ $5$ con coefficiente direttivo $1>0$ $1 > 0$ .
Proprietà (polinomio contro esponenziale, logaritmo contro potenza)
1. Polinomio contro esponenziale: $n^k \in o(a^n)$ se $k > 0$ , $a > 1$ (limite $n^k/a^n \to 0$ ; è la gerarchia degli infiniti di Limiti notevoli e gerarchia degli infiniti, che si può giustificare con il criterio del rapporto: $\dfrac{(n+1)^k/a^{n+1}}{n^k/a^n} = \dfrac{(1+1/n)^k}{a} \to \dfrac1a < 1$ , quindi il rapporto tende a $0$ , vedi Criteri del rapporto e della radice per successioni).
2. Logaritmo contro potenza: $(\log_b n)^k \in o(n^h)$ per $b > 1$ , $k, h > 0$ . Si pone $m = \log_b n$ : $n^h = (b^h)^m$ con $a = b^h > 1$ e $m^k \in o(a^m)$ per il punto 2.

Esempio. Per $n=100$ si ha $n^3=10^6$ mentre $2^n\approx1{,}3\cdot10^{30}$ , coerente con $n^3\in o(2^n)$ .

Cambio di base: $\log_b n = \log_a n \cdot \log_b a$ $lo g_{b} n = lo g_{a} n \cdot lo g_{b} a$ (Esponenziale e logaritmo), quindi $\log_b n \in \Theta(\log_a n)$ $lo g_{b} n \in Θ (lo g_{a} n)$ per basi costanti, perché $\log_b a$ $lo g_{b} a$ è una costante positiva. Esempio: $\log_{10} n = \log_2 n \cdot \log_{10} 2 \approx 0{,}301 \log_2 n$ $lo g_{10} n = lo g_{2} n \cdot lo g_{10} 2 \approx 0, 301 lo g_{2} n$ . Dentro la notazione la base si omette; fuori si assume $2$ $2$ . Inoltre $a^{\log_2 n} = n^{\log_2 a}$ $a^{l o g_{2} n} = n^{l o g_{2} a}$ (entrambi valgono $2^{\log_2 a \cdot \log_2 n}$ $2^{l o g_{2} a \cdot l o g_{2} n}$ , come si vede scrivendo $a = 2^{\log_2 a}$ $a = 2^{l o g_{2} a}$ e $n = 2^{\log_2 n}$ $n = 2^{l o g_{2} n}$ ).
Proprietà (legami tra le notazioni)
1. Legami tra notazioni:
  - $f \in o(g) \Rightarrow f \in O(g)$ (si prende $c = 1$ );
  - $f \in O(g) \iff g \in \Omega(f)$ (si divide per $c$ );
  - $f \in O(g)$ e $g \in O(f) \Rightarrow f \in \Theta(g)$ ;
  - $f \in O(g) \Rightarrow f + g \in \Theta(g)$ (perché $g \le f + g \le (c+1)g$ );
  - non valgono: $O \Rightarrow o$ ( $f = g = n$ ) né $O \Rightarrow \Theta$ ( $f = n$ , $g = n^2$ ).

Esempio. Con $f=n$ e $g=n^2$ : $f\in O(g)$ e $f\in o(g)$ , ma $f\notin\Theta(g)$ .

Sommatorie notevoli

Formula (sommatorie notevoli)

$\sum_{i=0}^{n} i = \frac{n(n+1)}{2}, \qquad \sum_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} \in \Theta(n^3), \qquad \sum_{i=0}^{n} a^i = \frac{a^{n+1} - 1}{a - 1}\ (a \ne 1).$

Come si ricavano (vedi Sommatorie; le prime due si dimostrano per induzione, Principio di induzione):

Prima formula (idea di Gauss). Scrivendo la somma $S=0+1+\dots+n$ due volte, la seconda in ordine inverso, e sommando termine a termine, ogni coppia vale $n$ e le coppie sono $n+1$ : $2S = n(n+1)$ .
Seconda formula. Il polinomio $\frac{n(n+1)(2n+1)}{6}$ ha grado $3$ (moltiplicando i tre fattori il termine di grado massimo è $\frac{2n^3}{6}=\frac{n^3}{3}$ ), quindi è $\Theta(n^3)$ . Controllo con $n=3$ : $0+1+4+9=14=\frac{3\cdot4\cdot7}{6}$ .
Terza formula (serie geometrica finita). Con $S=\sum_{i=0}^{n}a^i$ si ha $aS=\sum_{i=1}^{n+1}a^i$ ; sottraendo, tutti i termini intermedi si cancellano: $S-aS=1-a^{n+1}$ , da cui $S=\frac{a^{n+1}-1}{a-1}$ . Vedi Serie notevoli - geometrica, telescopica, armonica per il caso infinito. Per $a>1$ la somma è dominata dall'ultimo termine: $S \in \Theta(a^n)$ .

Esempio. $\sum_{i=0}^{10}i=\frac{10\cdot11}{2}=55$ e $\sum_{i=0}^{3}2^i=\frac{2^4-1}{2-1}=15$ .

Utili anche $\lfloor x \rfloor$ (più grande intero $\le x$ ), $\lceil x \rceil$ (più piccolo intero $\ge x$ ) e $x \bmod y$ (resto della divisione intera, % in C): $39 \bmod 7 = 4$ .

Terminologia

Complessità	Nome
$\Theta(\log n)$	logaritmica
$\Theta(n)$	lineare
$\Theta(n^2)$ , $\Theta(n^3)$	quadratica, cubica
$\Theta(n^k)$ , $k$ costante	polinomiale
$\Omega(a^n)$ , $a > 1$	esponenziale

Ordine crescente: $1 \prec \log n \prec \sqrt{n} \prec n \prec n \log n \prec n^2 \prec n^3 \prec 2^n$ (ogni funzione è $o$ della successiva). Per confrontare due espressioni si studia il limite del rapporto, come nella gerarchia degli infiniti: per esempio $n\log n / n^2 = \log n / n \to 0$ , quindi $n \log n \in o(n^2)$ .

Grafico interattivo: Crescita di n, n·log₂n, n² e 2ⁿ per n da 1 a 10 (numero di operazioni, asse verticale fino a 100): a n = 10 valgono 10, 33, 100 e 1024; l'esponenziale supera il quadrato già da n = 5 e esce dal grafico a n ≈ 6,6

Esempio svolto

Un algoritmo su un array $X$ di $n$ interi esegue $c_1 n$ operazioni per ogni intero pari e $c_2 \lceil \log_2 n \rceil$ per ogni dispari. Nel caso peggiore tutti gli elementi sono pari: $n \cdot c_1 n = c_1 n^2$ (più costanti), quindi $\Theta(n^2)$ . Limite superiore: ogni elemento costa al più $\max(c_1 n, c_2 \lceil \log_2 n \rceil) \le c' n$ , totale $\le c' n^2$ . Inferiore: l'istanza di soli pari costa $c_1 n^2$ . Il passaggio $\max(c_1 n, c_2 \lceil \log_2 n \rceil) \le c' n$ vale perché $\lceil \log_2 n \rceil \le n$ per ogni $n\ge1$ ( $\log_2 n$ cresce molto più lentamente di $n$ ), quindi basta prendere $c'=\max(c_1,c_2)$ .

Errori comuni

Confondere "è $O(n^2)$ " con "è quadratico": $O$ è solo un limite superiore, $3n + 4 \in O(n^2)$ è vero ma non stretto; per "esattamente" serve $\Theta$ .
Dire che $f \in O(g)$ implica $f \in \Theta(g)$ , o che $O$ implica $o$ .
Far dipendere $c$ o $n_0$ da $n$ .
Dimenticare che $\log$ senza base fuori dalla notazione è in base 2.

Versione ripasso

$O$ : $\exists c>0, n_0$ con $f(n) \le c\,g(n)$ per $n \ge n_0$ . $\Omega$ : $f(n) \ge c\,g(n)$ . $\Theta = O \cap \Omega$ . $o$ : per ogni $c>0$ vale $f \le c\,g$ definitivamente, cioè $\lim f/g = 0$ . Le costanti non dipendono da $n$ (vedi Complessità in tempo e caso pessimo).
Esempi: $3n+4 \in O(n)$ con $c=7, n_0=1$ ; $n+2n^2 \in \Theta(n^2)$ ; $100n \in o(n^2)$ con $n_0 = 100/c$ .
Theta: $\Theta=O\cap\Omega$ , cioè $c'\,g\le f\le c''\,g$ definitivamente. Esempio: $3n+4\in O(n)$ con $c=4$ , $n_0=4$ (perché $3n+4\le4n\iff n\ge4$ ); $3n+4\in\Omega(n)$ con $c=3$ .
Polinomi: $\sum_{i=0}^{k}a_i n^i\in\Theta(n^k)$ se $a_k>0$ (esempio: $(n+1)^5\in\Theta(n^5)$ , vedi Binomio di Newton).
Polinomio contro esponenziale: $n^k\in o(a^n)$ per $k>0$ e $a>1$ ; il criterio del rapporto dà $\frac{(1+1/n)^k}{a}\to\frac1a<1$ (vedi Criteri del rapporto e della radice per successioni). Logaritmo contro potenza: $(\log_b n)^k\in o(n^h)$ .
Basi: $\log_b n=\log_a n\cdot\log_b a$ , quindi $\log_b n\in\Theta(\log_a n)$ per basi costanti; dentro la notazione la base si omette.
Legami: $o\Rightarrow O$ ; $f\in O(g)\iff g\in\Omega(f)$ ; $f\in O(g)\Rightarrow f+g\in\Theta(g)$ . Non valgono $O\Rightarrow o$ (con $f=g=n$ ) né $O\Rightarrow\Theta$ (con $n$ e $n^2$ ).
Sommatorie notevoli (vedi Sommatorie): $\sum_{i=0}^n i=\frac{n(n+1)}{2}$ ; $\sum_{i=0}^n i^2=\frac{n(n+1)(2n+1)}{6}\in\Theta(n^3)$ ; $\sum_{i=0}^n a^i=\frac{a^{n+1}-1}{a-1}$ per $a\ne1$ , che per $a>1$ è $\Theta(a^n)$ . Idea di Gauss: sommando la somma con la sua copia rovesciata si ottiene $2S=n(n+1)$ . Controllo: $\sum_{i=0}^{3}i^2=14$ .
Terminologia: $\Theta(\log n)$ logaritmica, $\Theta(n)$ lineare, $\Theta(n^2)$ quadratica, $\Theta(n^3)$ cubica, $\Theta(n^k)$ polinomiale, $\Omega(a^n)$ con $a>1$ esponenziale. Ordine crescente: $1\prec\log n\prec\sqrt n\prec n\prec n\log n\prec n^2\prec n^3\prec 2^n$ .
Esempio: se ogni elemento pari costa $c_1 n$ e ogni dispari $c_2\lceil\log_2 n\rceil$ , il caso peggiore (tutti pari) è $\Theta(n^2)$ ; per il limite superiore si usa $\lceil\log_2 n\rceil\le n$ .
Forma di $g$ : va scelta la più semplice e la più vicina al vero andamento, senza costanti né termini minori: $\Theta(3n+2)$ si scrive $\Theta(n)$ .
Errori tipici: leggere $O$ come "esattamente" ( $3n+4\in O(n^2)$ è vero ma non stretto); concludere $O\Rightarrow\Theta$ ; far dipendere $c$ o $n_0$ da $n$ ; dimenticare che $\log$ senza base fuori dalla notazione è in base $2$ .