Notazione asintotica

Serve a stimare il tempo massimo necessario per l’esecuzione di un algoritmo, conoscere il tipo di crescita del tempo di esecuzione al crescere della dimensione delle istanze di input, confrontare le prestazioni di algoritmi diversi per lo stesso problema e stabilire la difficoltà dei problemi.

Notazione O-grande

Date due funzioni $f:\mathbb{N}\to {\mathbb{R}}_{+}$ e $g:\mathbb{N}\to {\mathbb{R}}_{+}$ diremo che $f(n)\in O(g(n))$ SE E SOLO SE esistono due costanti $c>0$ e $n_0\in \mathbb{N}$ tali che $f(n)\le cg(n)$ per ogni $n\ge n_0$.

PROPOSIZIONE Per ogni costante $a>0$ vale che SE $f(n)\in O(g(n))$ ALLORA $a\cdot f(n)\in O(g(n))$. In sostanza le costanti non influenzano la grandezza della funzione.

Somma di funzioni SE $d(n)\in O(f(n))$, e $e(n)\in O(g(n))$ ALLORA $d(n)+e(n)\in O(max\{f(n),g(n)\})$.

Prodotto di funzioni Una cosa simile vale per la moltiplicazione SE $d(n)\in O(f(n))$, e $e(n)\in O(g(n))$ ALLORA $d(n)\cdot e(n)\in O(f(n)\cdot g(n))$.

Transitività SE $d(n)\in O(f(n))$, e $f(n)\in O(g(n))$ ALLORA $d(n)\in O(g(n))$.

PROPOSIZIONE Per ogni coppia di costanti $a>1,x>0$ vale che $n^x\in O(a^n)$ Esempio: $n^{100}=O(2^n)$

PROPOSIZIONE Per ogni costante $k>1$ abbiamo che $a_k{n}^k+a_{k-1}{n}^{k-1}+...+a_{1}n+a_0\in O(n^k)$ Quindi un polinomio di grado massimo $k$ è $=(n^k)$.

PROPOSIZIONE $\log n\in O(n)$

Si deve dimostrare che ${\log }_{2}n\le cn$ Dimostrazione per induzione

1. Caso base $n=1\Rightarrow \log n=\log 1=0\le 1=c\cdot n$ $\log n\le n,\forall n\ge 1$
2. Ipotesi induttiva: $\log n\le n$ La tesi da dimostrare è: $\log (n+1)\le (n+1)$ Per dimostrarlo, si ha: \begin{align} \log(n+1) &\le log(n+n) \\ & = log(2n) \\ & = \log 2 + \log n \\ & = 1+n \mbox{ (per l'ipotesi induttiva)} \end{align}

Notazione Omega

Date due funzioni $f:\mathbb{N}\to {\mathbb{R}}_{+}$ e $g:\mathbb{N}\to {\mathbb{R}}_{+}$ diremo che $f(n)\in \Omega (g(n))$ SE E SOLO SE esistono due costanti $c>0$ e $n_0\in \mathbb{N}$ tali che $f(n)\ge cg(n)$ per ogni $n\ge n_0$.

Attenzione! $f(n)\in \Omega (g(n))⟺g(n)\in O(f(n))$

Notazione Theta

Date due funzioni $f:\mathbb{N}\to {\mathbb{R}}_{+}$ e $g:\mathbb{N}\to {\mathbb{R}}_{+}$ diremo che $f(n)\in \Theta (g(n))$ SE E SOLO SE esistono tre costanti $c_1,c_2>0$ e $n_0\in \mathbb{N}$ tali che $c_{1}g(n)\le f(n)\le c_{2}g(n)$ per ogni $n\ge n_0$.

asd_07