Projet : calcul de complexité

Les lignes 1, 5 et 9 définissent des blocs, les autres sont des instructions composées d'instructions basiques (affectations, sommes et lectures) toutes en $\mathcal{O}(1)$ : la complexité va être égale au nombre de fois où chaque ligne est exécutée. Calculons la en regroupant les lignes de l'algorithme en paquets :

1. boucle 5-7
2. boucle 9-11
3. le reste

Les lignes du paquet 1 vont être exécutées autant de fois que la boucle va itérer, c'est à dire début.longueur fois. La complexité du paquet 1 est donc : $\mathcal{O}(1) \cdot \mbox{début.longueur} = \mathcal{O}(\mbox{début.longueur})$

De la même manière, les lignes du paquet 2 vont être exécutées autant de fois que la boucle va itérer, c'est à dire fin.longueur fois. La complexité du paquet 2 est donc : $\mathcal{O}(\mbox{fin.longueur})$.

Enfin, les lignes du paquet 3 vont toutes être exécutées 1 fois : la complexité totale de l'exécution de toutes les lignes du paquet 3 va être $\mathcal{O}(1)$.

La complexité totale est donc en $\mathcal{O}(\mbox{début.longueur} + \mbox{fin.longueur})$.

Toutes les lignes sont en $\mathcal{O}(1)$ et deux boucles de $\mathcal{O}(\mbox{t.longueur})$ itérations.

La complexité est donc en $\mathcal{O}(1) + 2\cdot\mathcal{O}(\mbox{t.longueur}) = \mathcal{O}(\mbox{t.longueur})$

L'algorithme est récursif calculer sa complexité va dépendre d'une équation récurrente. Une analyse rapide de l'algorithme nous indique que cette équation de récursion est basée sur la taille du tableau en entrée, on note alors $C(n)$ la complexité de supprime_rec pour un tableau de taille $n$ passé en entrée.

Regardons la complexité de l'algorithme ligne à ligne :

• lignes 1 à 4 : chaque ligne est en $\mathcal{O}(1)$. Complexité totale de ce paquet : $\mathcal{O}(1)$
• lignes 6 à 7 : une boucle de $n-1 = \mathcal{O}(n)$ itérations. Comme chaque ligne de la boucle est en $\mathcal{O}(1)$, la complexité totale de ce paquet est : $\mathcal{O}(n)$
• lignes 9 à 12 : selon la valeur du test soit la ligne 10 soit la ligne 12 est exécutée.

Il faut faire très attention pour ce genre de lignes car :

• un des paramètres de l'appel à concaténationle résultat de l'appel récursif
• la complexité de la fonction concaténation n'est pas $\mathcal{O}(1)$, on ne peut donc pas l'ignorer dans nos calculs.

Ces deux lignes sont de même complexité : $C(n-1) + \mathcal{O}(n)$. Le premier terme correspond au calcul du second paramètre de l'appel à la fonction concaténation et le second à la complexité de l'exécution de concaténation.

On a maintenant assez pour écrire l'équation qui régit la complexité :

Cette équation se résout simplement :

L'algorithme itératif est bien meilleur que l'algorithme récursif : $\mathcal{O}(n)$ versus $\mathcal{O}(n^2)$ si $n$ est la taille du tableau passé en paramètre.

Ceci est du à la duplication du tableau dans la version récursive qui ajoute un facteur $\mathcal{O}(n)$ à chaque récursion.

Pour que les complexités soient comparables il faudrait pouvoir ajouter petit à petit des éléments au tableau ce qui est impossible. Les algorithmes récursifs préfèrent utiliser des structures dynamiques comme les listes qui permettent d'ajouter efficacement des objets à un conteneur. Nous verrons ces structures plus tard dans le cours.

L'algorithme est récursif et toutes les lignes à part l'appel récursif sont en $\mathcal{O}(1)$. Comme la condition d'arrêt de la récursion se passe sur le second paramètre, on peut écrire l'équation de récurrence :

Avec $C(n/2) = \mathcal{O}(1)$ si $n$ est la taille du tableau. La complexité maximale sera atteinte pour $i = 0$ et dans ce cas :

TBD.

On a clairement que $b-a$ est divisé par 2 à chaque itération, il y a donc autant d'itérations que l'on peut diviser $t.{\small longueur}$ par 2.

Si $K$ est le nombre d'itérations, on a que : $2^{K} \leq t.{\small longueur}$. Il existe un nombre $p$ tel que $2^p \leq t.{\small longueur} < 2^{p + 1}$. On ne peut donc pas diviser $t.{\small longueur}$ par 2, ou un nombre plus petit que lui, plus de $p$ fois. Ce nombre est exactement la partie entière de $\log_2(t.{\small longueur})$ puisque :

On en conclut le théorème fondamental d la dichotomie : le nombre de fois où l'on peut diviser par 2 un nombre $n$ est $\log_2(n)$.

$M^k(91) = M^k(M(102)) = M^k(92) = \dots = M^k(101) = M^{k-1}(91)$

• si $n > 100$ il y a 1 appel,
• si $101 > n > 90$, il y 2 appels pour passer $M(n)$ à $M(n+1)$. Donc au plus 19 appels pour aller de $M(91)$ à $M(100)$ qui se calcule en 2 appels $M(100) = M(M(111)) = M(101) = 91$.
• sinon, $n \leq 90$ et $M(n)$ sera égal à un $M^k(n')$ avec $90 < n' < 101$. Le maximum sera atteint pour $n=1$ en 11 appels, $M^{11}(111) = M^{10}(101) = M^{9}(91)$.

Le nombre d'appel maximum sera atteint pour $n=1$. Dans ce cas là Au pire il faudra 13 appels pour arriver à $M^{9}(91)$, puis 21 appels pour arriver à $M^{8}(91)$, puis encore $7 \cdot 21$ appels pour arriver à $M(91)$ qui se calcule en 20 appels supplémentaires.

Une borne sera donc de $13 + 21 \cdot 8 + 20 = 201$ appels.

Une vérification expérimentale possible en python :

compte = [0]

def M(n):
  compte[0] += 1
  # print("    ", compte[0], n)

  if n > 100:
    return n - 10
  else:
    return M(M(n+11))

max_compte = 0

for n in range(1, 102):
  compte[0] = 0
  m = M(n)
  # print("n =", n, "M = ", m, "compte =", compte[0])
  max_compte = max(max_compte, compte[0])
print("max =", max_compte)