Analyse et complexité amortie
L'analyse amortie (et la complexité amortie qui en découle) est une technique utilisée pour calculer la complexité lorsque plusieurs exécutions successives d'un même bloc de code va être de complexités différentes.
Par l'exemple lors de l'utilisation de structures complexes où les instructions coûteuses ne sont faites qu'un petit nombre de fois lorsque l'on exécute la méthode plusieurs fois (comme pour les listes par exemple).
Ce n'est pas une complexité en moyenne, c'est un moyen de calculer des complexités (maximum)
Définitions
Si lors de l'exécution d'un algorithme $A$, une opération $O$ (ou une fonction) de celui-ci se répète plusieurs fois et que sa complexité diffère selon les appels, le calcul de la complexité de $A$ va nécessiter une analyse fine de de toutes les exécutions de l'opération $O$ car borner la complexité par le maximum conduit (souvent) à surestimer grandement la complexité réelle.
Définition
L'analyse amortie est regroupe un ensemble des techniques permettant de calculer globalement la complexité maximale $C$ de $m$ exécutions successives d'un algorithme.
La complexité amortie de cet algorithme est alors $\frac{C}{m}$.
Il ne faut pas le confondre avec la complexité en moyenne, c'est bien $m$ fois la complexité maximale que l'on considère lorsque l'on effectue les opération successivement.
Méthodes d'analyse amortie
Complexité amortie
Exercices
Entraînons nous à comprendre puis à maîtriser ce concept.
Analyse amortie
Reprenons l'exemple de la Pile et de sa méthode k-dépile utilisée dans la partie complexité amortie.
Calculer la complexité de l'algorithme $A$ en utilisant l'analyse par agrégat.
corrigé
corrigé
Au cours des $m$ exécutions, on peut considérer ue l'on a fait appel :
- $m'$ fois à la fonction
k-dépile, - $m''$ fois à la fonction
empile, - $m - m' - m''$ fois à la fonction
nombre.
Le nombre total d'éléments dépilés au cours des $m'$ exécutions de la fonction k-dépile ne peut excéder le nombre total $m''$ d'éléments empilés. La complexité totale des $m'$ exécutions de k-dépile vaut donc $\mathcal{O}(m' + m'')$.
Comme la complexité d'un appel à empile ou à nombre vaut invariablement $\mathcal{O}(1)$, on en conclut que la complexité totale recherchée vaut :
$$ C = \mathcal{O}(m' + m'') + \mathcal{O}(m'') + \mathcal{O}(m - m' - m'') = \mathcal{O}(m + m'') = \mathcal{O}(m) $$
Calculer la complexité de l'algorithme $A$ en utilisant l'analyse par potentiel.
Pourquoi est-il judicieux d'utiliser comme potentiel le nombre d'élément dans la pile après l'exécution de l'instruction $i$ ?
corrigé
corrigé
Soit $\Omega(i)$ le nombre d'élément dans la pile après l'exécution de l'instruction $i$. Ce potentiel est motivé par le fait que la seule méthode ayant un coût variable est k-dépile et elle dépend du nombre d'éléments à dépiler, c'est à dire indirectement au nombre d'élément dans la pile.
Comme la pile est initialement vide on a bien $\Omega(i) \geq \Omega(0)$ pour tout $i$. Le coût amorti de chaque opération est alors :
- le coût amorti de
nombreest $1$ puisque la pile de change pas $\Omega(i) = \Omega(i - 1)$ - le coût amorti de
empileest $2$ puisque le coût réel est 1 et la pile à un élément de plus après l'opération ($\Omega(i) = \Omega(i - 1) + 1$) - le coût amorti de
k-dépileest $1$ puisque le coût réel est de $1 + k$ et la pile à $k$ éléments de moins après l'opération ($\Omega(i) = \Omega(i - 1) - k$)
Le coût amorti peut être borné par 2 pour chaque opération, on a donc :
$$ C \leq \sum_{i=1}^m \widehat{c_i} \leq \sum_{i=1}^m 2 = 2 \cdot m = \mathcal{O}(m) $$
Calcul de complexité amortie
C'est l'exercice 4 de cette planche d'exercices
On calcule la complexité amortie de $m$ exécutions successives exécutions de l'algorithme $A$. On note $c(i)$ la complexité de la $i$ ème exécution.
On vous demande de calculer la complexité amortie en $\mathcal{O}$ de l'exécution de $A$ pour différentes valeurs de $c(i)$.
corrigé
corrigé
La complexité totale vaut :
La complexité amortie est en $\mathcal{O}(1)$.
$c(i)$ vaut la plus petite puissance de 2 divisant $i$
corrigé
corrigé
pour les $m$ itérations :
- la moitié est divisible uniquement par 2
- le quart est divisible uniquement par 4
- ...
- $\frac{1}{2^k}$ est divisible uniquement par $2^k$
La complexité totale vaut alors :
La complexité amortie est en $\mathcal{O}(\ln(m))$
$c(i)$ vaut le plus grand $k$ tel que $2^k$ divise $i$
corrigé
corrigé
Le calcul est presque identique à l'exercice précédent. La complexité totale vaut alors :
Comme $\sum_{0\leq k \leq n}\frac{k}{2^k} \leq 2$ (on l'a vu), on a $C \leq 2m$ et la complexité amortie est en $\mathcal{O}(1)$
File et pile
On reprend l'exercice de construction d'une file avec deux piles
Quelle est la complexité amortie de $m$ enfilage et défilage avec cette structure ?
corrigé
corrigé
On peut calculer la complexité totale par méthode comptable exactement comme note pile avec la méthode k-dépile. En effet une fois enfilé une donnée ne sera placée dans la seconde pile qu'une seule fois.
On obtient la même fonction de coût et donc la même complexité amortie : $\mathcal{O}(1)$. Cette structure qui semblait un brin fantaisiste est donc tout aussi optimale que la structure classique de file en complexité.
Ajout et suppression dans une liste
TBD faire un mix avec 8.2 : https://www.di.ens.fr/~fouque/articles/poly-algo.pdf avec comptage et potentiel pour l'ajout simple. TBD voir aussi le poly de pascal. TBD à faire (dire que c'est dur)
$N$ utilisations successives des méthodes d'ajout ou de suppression du dernier élément d'une liste prend $\mathcal{O}(N)$ opérations au maximum.
preuve
preuve
TBD le faire.
Ajout et suppression dans série de listes triées
TBD pas évident de pourquoi on fait ça : ie réduire le coup d'insertion. Reprendre l'idée du compteur. exercice 3 : https://perso.ens-lyon.fr/laureline.pinault/Algo1/TD06-correction.pdf