# Algorithme du lièvre et de la tortue

L'algorithme du lièvre et de la tortue, également connu sous le nom d'algorithme de détection de cycle de Floyd, est un algorithme pour détecter un cycle dans une suite récurrente engendrée par une certaine fonction f définie d'un ensemble fini S dans lui-même. Alors qu'un algorithme naïf consisterait à stocker chaque élément de la suite et, à chaque étape, de vérifier si le nouvel élément fait partie des éléments déjà rencontrés, l'algorithme de Floyd, lui, utilise un espace constant. L'algorithme a un bon comportement quand la fonction f a un comportement pseudo-aléatoire, et celui-ci peut être analysé par le paradoxe des anniversaires.
L'algorithme est sommairement décrit en 1969 par Donald Knuth dans un exercice du volume 2 de The Art of Computer Programming et attribué à Robert Floyd sans autre précision. Il est aussi décrit dans la note 3.8 de et est aussi attribué à Robert W. Floyd. Contrairement à ce que l'on trouve parfois, il n'est pas décrit dans un article de 1967 de ce dernier.
L'algorithme rho de Pollard pour la décomposition en nombres premiers de même que celui pour le calcul du logarithme discret utilisent tous deux l'algorithme de détection de cycle de Floyd, pour des suites pseudo-aléatoires particulières.

## Suite ultimement périodique

Soit $f\colon S\rightarrow S$ une fonction, et S un ensemble fini de cardinal n. On considère la suite $(a_{i})$ définie par $a_{0}\in S$ et $a_{i+1}=f(a_{i})$. Cette suite possède un cycle, car le nombre de ses valeurs possibles est majoré par n. Knuth dit que la suite est ultimement périodique , cela signifie que les valeurs
a$_0$, a$_1$, … a$_λ$, … a$_{λ+μ-1}$
sont distinctes et a$_{n+μ}$ = a$_n$ pour tout n ≥ λ (μ est la longueur du cycle et λ le nombre d'éléments à l'extérieur du cycle).
La suite dessinée ressemble à la lettre grecque ρ, comme montré sur la figure ci-contre. Si l'on parvient à trouver deux indices i < j avec $a_{i}=a_{j}$ alors j-i est un multiple de la longueur du cycle.

## Principe

L'algorithme de Floyd de détection de cycle repose sur la propriété suivante : si la suite admet un cycle, alors il existe un indice m avec $a_{m}=a_{2m}$ et λ ≤ m ≤ λ+μ. Ainsi, l'algorithme consiste à parcourir la séquence simultanément à deux vitesses différentes : à vitesse 1 pour la tortue et à vitesse 2 pour le lièvre. Autrement dit, l'algorithme inspecte les couples :
(a$_1$, a$_2$), (a$_2$, a$_4$), (a$_3$, a$_6$), (a$_4$, a$_8$), etc.
L'algorithme trouve le premier indice m tel que $a_{m}=a_{2m}$. Dès lors, $2m-m=m$ est un multiple de la longueur du cycle μ.
Pour déterminer la valeur exacte de μ, il suffit de refaire tourner l'algorithme à partir de m+1, jusqu'à trouver un autre nombre $m_{1}$ tel que $a_{m_{1}}=a_{2{m_{1}}}$. Dès lors on a d'une part $m_{1}\leq m+\mu$ (car on retombe alors sur $a_{m}$) et d'autre part μ qui divise $m_{1}-m$ (car il divise $m$ et $m_{1}$), donc $\mu =m_{1}-m$.

### Exemple

La séquence démarre en bas, monte et emprunte le cycle dans le sens des aiguilles d'une montre (voir figure). Suivant l'algorithme de Floyd, les deux parcours se rencontrent en $a_{6}$ après 6 itérations. Un deuxième tour de l'algorithme amène les deux parcours à se rencontrer après 6 nouvelles itérations, d'où la valeur $\mu =6$.
| Parcours | $t_{1}$ | $t_{2}$ | $t_{3}$ | $t_{4}$ | $t_{5}$ | $t_{6}$ | $t_{7}$ | $t_{8}$ | $t_{9}$ | $t_{10}$ | $t_{11}$ | $t_{12}$ |
| Lent (tortue) | $a_{1}$ | $a_{2}$ | $a_{3}$ | $a_{4}$ | $a_{5}$ | $a_{6}$ | $a_{7}$ | $a_{2}$ | $a_{3}$ | $a_{4}$ | $a_{5}$ | $a_{6}$ |
| Rapide (lièvre) | $a_{2}$ | $a_{4}$ | $a_{6}$ | $a_{2}$ | $a_{4}$ | $a_{6}$ | $a_{2}$ | $a_{4}$ | $a_{6}$ | $a_{2}$ | $a_{4}$ | $a_{6}$ |

### Complexité

La complexité en temps peut-être mesurée par le nombre de comparaisons. L'algorithme effectue au minimum λ comparaisons, étant donné que le parcours lent de la séquence doit au moins atteindre le cycle pour rencontrer le parcours rapide. Le nombre maximum de comparaisons est $\lambda +\mu$, étant donné que le parcours lent ne peut effectuer plus d'un tour du cycle avant d'être rattrapé par le parcours rapide. L'algorithme utilise un espace O(1).

## Pseudo-code
### Calcul de la longueur du cycle

Si on souhaite obtenir la valeur de $\mu$, il suffit d'ajouter à la suite le code suivant :

## Améliorations

Brent a amélioré l'algorithme du lièvre et de la tortue. Il prétend qu'il est 36% plus rapide que l'algorithme du lièvre et de la tortue classique. Il améliore l'algorithme rho de Pollard de 24%.