Outils mathématiques pour l'analyse de complexité
Quelques outils mathématiques pour l’analyse de complexité des algorithmes.
Suites
- $\left(u_k\right)_{k \in \mathbb{N}}$ représente une suite de terme $u_k$ pour $k \in \mathbb{N}$
- $\left(u_k\right)_{k \in K}$ représente la sous-suite extraite pour la famille d’indices $K \subseteq \mathbb{N}$
- $\left(\sum_{k=a}^{b} u_k\right)$ est la somme des termes $u_k$ tels que $a \le k \le b$
- $\left(\prod_{k=a}^{b} u_k\right)$ est le produit des termes de $u_k$ tels que $a \le k \le b$
NB: par convention usuelle en informatique si $a > b$, alors:
- $\left(\sum_{k=a}^{b} u_k\right) = 0$ (élément neutre de la somme)
- et $\left(\prod_{k=a}^{b} u_k\right) = 1$ (élément neutre du produit)
Arithmétique
- opérateurs usuels: $+$, $-$, $\times$, $/$, $<$, $\le$, $\ge$, $>$, $=$, $\neq$, …
- factorielle: $n!$ est le produit des entiers de $1$ à $n$
Pour un nombre réel $x$ positif ou nul:
- $\lfloor x \rfloor$ est la partie entière (inférieure) de $x$, c’est à dire le plus grand entier $k \in \mathbb{N}$ tel que $k \le x$
- $\lceil x \rceil$ est la partie entière supérieure de $x$, c’est à dire, le plus petit entier $k \in \mathbb{N}$ tel que $x \le k$
Propriétés des parties entières
Pour tous réels positifs ou nuls $x, y$ et tout entier $n \in \mathbb{N}$:
- $n = \lfloor n / 2 \rfloor + \lceil n / 2 \rceil$
- $\lfloor x \rfloor = n$ si et seulement si $n \le x < n+1$
- $\lceil x \rceil = n$ si et seulement si $n-1 < x \le n$
- $\lfloor x + n \rfloor = \lfloor x \rfloor +n$
- $\lceil x + n \rceil = \lceil x \rceil + n$
- $\lfloor x \rfloor < n$ si et seulement si $x < n$
- $\lceil x \rceil \le n$ si et seulement si $x \le n$
- $n < \lceil x \rceil$ si et seulement si $n < x$
- $n \le \lfloor x \rfloor$ si et seulement si $n \le x$
- $\lfloor x \rfloor + \lfloor y \rfloor \le \lfloor x + y \rfloor \le \lfloor x \rfloor + \lfloor y \rfloor + 1$
- $\lceil x \rceil + \lceil y \rceil - 1 \le \lceil x + y \rceil \le \lceil x \rceil + \lceil y \rceil$
Fonctions exponentielle et logarithme
La fonction exponentielle $\exp$ est définie sur $\mathbb{R}$ et continue. Pour tous réels $x$ et $y$:
- $\exp(x) = e^x$ où $e$ est la constante de Néper ou nombre d’Euler
- $\exp(x) \cdot \exp(y) = \exp(x+y)$
- $\exp(-x) = \frac{1}{\exp(x)}$
La fonction logarithme népérien $\ln$ est définie $\mathbb{R}_+^*$ et continue. Pour tout réels positifs et non-nuls $x$ et $y$:
- $\ln(x \cdot y) = \ln(x) + \ln(y)$
- $\ln(\frac{1}{x}) = -\ln(x)$
- $\ln(e) = 1$ où $e$ est la constante de Néper ou nombre d’Euler
Les fonctions exponentielle et logarithme népérien sont duales l’une de l’autre:
\[\exp(x) = y \quad \text{ssi} \quad x = \ln(y) \qquad \text{pour tout réels } x, y \text{ tels que } y > 0\]- $\exp(\ln(y)) = y$ pour tout réel positif et non nul $y$
- $\ln(\exp(x)) = x$ pour tout réel $x$
On en déduit, pour tout réel $x > 0$ et $n \in \mathbb{N}$:
- $x^n = \exp(\ln(x))^n = \exp(n \cdot \ln(x))$
Pour l’analyse de complexité, on utilise différentes fonctions logarithme:
- $\ln$ est le logarithme népérien, de base $e$
- $\log_b$ est le logarithme de base $b$: $\log_b(x) = \frac{\ln(x)}{\ln(b)}$ pour tous réels $x, b > 0$
- en particulier, $\log_2(x)$ est le logarithme binaire: $\log_2(x) = \frac{\ln(x)}{\ln(2)}$ pour $x>0$
- enfin, $\log(x)$ dénote une fonction logarithme sans base précise (c’est à dire, à une constante multiplicative près)
Pour tous réels $x,y,a$ tels que $a, y > 0$:
\[a^x = y \text{ si et seulement si } x = \log_a(y)\]Comparaison asymptotique de fonctions
Notations de Landau
Soient $f$ et $g$ deux fonctions de $\mathbb{N}$ dans $\mathbb{N}$.
-
$f$ est grand-$\Omicron$ de $g$, noté $f \in \Omicron(g)$, s’il existe une constante réelle $c > 0$ (facteur multiplicatif) et une constante entière $n_0 \in \mathbb{N}$ (seuil) telles que:
\[f(n) \le c \cdot g(n) \text{ pour tout } n \ge n_0\] -
$f$ est Omega de $g$, noté $f \in \Omega(g)$, s’il existe une constante réelle $c > 0$ (facteur multiplicatif) et une constante entière $n_0 \in \mathbb{N}$ (seuil) telles que:
\[f(n) \ge c \cdot g(n) \text{ pour tout } n \ge n_0\] -
$f$ est Théta de $g$, noté $f \in \Theta(g)$, s’il existe deux constantes réelles $c_1, c_2 > 0$ (facteurs multiplicatifs) et une constante entière $n_0 \in \mathbb{N}$ (seuil) telles que:
\[c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) \text{ pour tout } n \ge n_0\] -
$f$ est petit-$\omicron$ de $g$, noté $f \in \omicron(g)$, si pour toute constante $\varepsilon > 0$ (facteur multiplicatif), il existe une constante entière $n_0 \in \mathbb{N}$ (seuil) telle que:
\[f(n) \le \varepsilon \cdot g(n) \text{ pour tout } n \ge n_0\]en d’autres termes: $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$
Intuition:
- si $f \in \Omicron(g)$ alors $f$ est asymptotiquement majorée par une fonction proportionnelle à $g$
- si $f \in \Omega(g)$ alors $f$ est asymptotiquement minorée par une fonction proportionnelle à $g$
- si $f \in \Theta(g)$ alors $f$ et $g$ sont asymptotiquement du même ordre de grandeur (minorée et majorée par des fonctions proportionnelles à $g$)
- si $f \in \omicron(g)$ alors $f$ est asymptotiquement négligeable face à $g$
Notations: on écrit parfois $f = \Omicron(g)$ au lieu de $f \in \Omicron(g)$, et de même pour $\Omega$, $\Theta$ et $\omicron$.
Propriétés
Soit des fonctions $f$, $g$ et $h$ de $\mathbb{R}$ dans $\mathbb{R}$.
- $f \in \Omicron(g)$ si et seulement si $g \in \Omega(f)$
- $f \in \Theta(g)$ si et seulement si $f \in \Omicron(g)$ et $f \in \Omega(g)$
- si $f \in \omicron(g)$ alors $f \in \Omicron(g)$ et $g \notin \Omicron(f)$
Symmétrie de $\Theta$
- $f \in \Theta(g)$ si et seulement si $g \in \Theta(f)$
Réflexivité
Pour tout $X \in \set{\Omicron, \Omega, \Theta}$ on a $f \in X(f)$
Arithmétique
Soient $f, g, h, l$ des fonctions positives et $a, b > 0$ des constantes. Ci-dessous $X$ représente n’importe quel opérateur $\Omicron$, $\Omega$, $\Theta$ et $\omicron$.
- transitivité: si $f \in X(g)$ et $g \in X(h)$ alors $f \in X(h)$
- linéarité: si $f, g \in X(g)$ alors $af + bh \in X(h)$
- produit: si $f \in X(h)$ et $g \in X(l)$ alors $fg \in X(hl)$
- si $g \in \Omega(h)$ alors $af + bg \in \Omega(h)$
Comparaison de familles de fonctions
Une polynôme de degré $d \in \mathbb{N}$ est une fonction définie sur $\mathbb{R}$ par: $f(x) = a_d x^d + a_{d-1} x^{d-1} + \dots + a_1 x + a_0$ telle que $a_d \neq 0$.
- soit $f$ un polynôme de degré $d$, alors $f \in \Theta(x^d)$
- pour tous nombres réels $a, b$ tels que $a > 1$, $n^b \in \omicron(a^n)$: une fonction exponentielle de base $a > 1$ quelconque croît plus rapidement que toute fonction polynômiale
- pour tous nombres réels $a, b > 0$, $(\ln n)^b \in \omicron(n^a)$: une fonction polynômiale de coefficient dominant positif croît plus rapidement que toute fonction (poly)logarithmique
Séries
L’analyse de complexité fait souvent intervenir la somme des termes de séries particulières.
Série arithmétique
Une suite arithmétique est une suite de la forme $u_{n+1} = u_n + r$ où $r \in \mathbb{R}$ est la raison de la suite. Le terme général de la suite est $u_n = u_0 + n \cdot r$. La différence entre deux termes successifs d’une suite arithmétique est constante et égale à $r$.
La somme des termes est définie par:
\[\sum_{i=0}^n u_i = (n+1) \cdot u_0 + \frac{n(n+1)r}{2}\]En particulier, la série divergente $\left(\sum_{i=1}^{\infty} i\right) = 1 + 2 + \ldots + n + \ldots$ est définie par la suite arithmétique de raison $r = 1$ et de terme initial $u_0 = 0$.
On en déduit:
\[\left(\sum_{i=1}^n i\right) = \frac{n \cdot (n+1)}{2} \in \Theta(n^2)\]Série géométrique
Une suite géométrique est une suite de la forme $u_{n+1} = r \cdot u_n$ où $r \in \mathbb{R}$ est la raison de la suite. Le terme général de la suite est $u_n = u_0 \cdot r^n$. Le ratio entre deux termes successifs d’une suite géométrique est constant et égal à $r$.
La somme des termes d’une suite géométrique de raison $r \neq 1$ est définie par:
\[\sum_{i=0}^n u_i = u_0 \cdot \frac{1-r^{n+1}}{1-r}\]NB: $n+1$ est le nombre de termes de la somme.
En particulier, la série $\left(\sum_{i=0}^{\infty} x^i\right)$ est définie par la série géométrique de raison $x$. Elle converge si et seulement si $|x| < 1$, alors:
\[\sum_{i=0}^{\infty} x^i = \frac{1}{1-x} \in \Omicron(1) \quad \text{ si } |x| < 1\]Série harmonique
La série harmonique est la somme des inverses des entiers naturels non nuls:
\[\sum_{i=1}^{\infty} \frac{1}{i} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots\]Cette série est définie par la suite harmonique:
\[H_n = \sum_{i=1}^n \frac{1}{i}\]On peut montrer que $H_n \in \Theta(\ln(n))$
Séries remarquables convergentes
Les séries $\left(\sum_{i=1}^{\infty} \frac{1}{i^2}\right)$ et $\left(\sum_{i=1}^{\infty} \frac{1}{2^i}\right)$ sont convergentes, et donc $\Omicron(1)$.
Résolution des récurrences de partitions
Cas général
Une équation de récurrence de partitions est de la forme:
\[T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n)\]où $n \in \mathbb{N}$, $a$ et $b$ sont deux constantes entières telles que $a \geq 1$ et $b > 1$ et $f$ est une fonction de $\mathbb{N}$ dans $\mathbb{R}_+$.
Le théorème général (Master theorem en anglais) donne une borne asymptotique pour $T(n)$ en fonction de $a$, $b$ et $f$:
- si $f(n) \in \Omicron(n^c)$ avec $c < \log_b(a)$ alors $T(n) \in \Theta(n^{\log_b(a)})$
- si $f(n) \in \Theta(n^c \cdot \log^k(n))$ avec $c = log_b(a)$ et une constante $k \ge 0$, alors $T(n) \in \Theta(n^c \cdot \log^{k+1}n)$
- si $f(n) \in \Omega(n^c)$ avec $c > \log_b(a)$ et s’il existe deux constantes $k < 1$ et $n_0 \in \mathbb{N}$ telles que pour $n \ge n_0$, $a\cdot f\left(\frac{n}{b}\right) \le k\cdot f(n)$, alors $T(n) \in \Theta(f(n))$.
NB: le théorème général résout l’équation de récurrence uniquement pour certaines valeurs de $a$, $b$ et $f$.
Cas où $f(n)$ est polynômialement majorée
Lorsque $f(n)$ est majorée par un polynôme de degré $d \in \mathbb{N}$, c’est à dire $f(x) \in \Omicron(n^d)$:
\[T(n) = a \cdot T\left(\frac{n}{b}\right) + \Omicron(n^d)\]Alors, le théorème général donne une borne asymptotique à $T(n)$ pour toutes valeurs de $a \ge 1$, $b > 1$ et $d \in \mathbb{N}$:
- si $d < \log_b(a)$ alors $T(n) \in \Omicron(n^{\log_b(a)})$
- si $d = \log_b(a)$ alors $T(n) \in \Omicron(n^d \cdot \log_b(n))$
- si $d > \log_b(a)$ alors $T(n) \in \Omicron(n^d)$