Preuves et complexités

Algorithme d’Euclide étendu

On rappelle la définition de l’algorithme en Python.

In [1]: def bezout(a, b):
   ...:     s, t, u, v = 1, 0, 0, 1
   ...:     while b != 0:
   ...:         q = a // b
   ...:         a, s, t, b, u, v = b, u, v, a - q * b, s - q * u, t - q * v
   ...:     return (a, s, t) if a > 0 else (-a, -s, -t)     # Le pgcd doit être positif
   ...: 

Tout d’abord, l’algorithme se termine car b est un entier naturel qui décroît strictement à chaque itération de la boucle while.

Ensuite, en notant \(a_0\) et \(b_0\) les valeurs initiales de \(a\) et \(b\), on peut prouver que les égalités \(a_0s+b_0t=a\) et \(a_0u+b_0v=b\) sont des invariants de boucle.

Comme à la fin de l’algorithme, \(b\) vaut le pgcd de \(a_0\) et \(b_0\) (cf. Preuve d’un algorithme), l’algorithme fournit bien le résultat attendu.

Recherche par dichotomie

On rappelle l’algorithme en Python.

In [2]: def appartient_dicho(elt, lst):
   ...:     g = 0
   ...:     d = len(lst) - 1
   ...:     while g <= d:
   ...:         m = (g + d) // 2
   ...:         if lst[m] == elt:
   ...:             return True
   ...:         if elt < lst[m]:
   ...:             d = m - 1
   ...:         else:
   ...:             g = m + 1
   ...:     return False
   ...: 

Notons \(n\) la taille de la liste où on recherche l’élément.