La Complexité des Algorithmes Récursifs

5.1 Analyse de la complexité des algorithmes récursifs.

Les algorithmes récursifs sont un outil puissant pour résoudre des problématiques complexes, en les décomposant en sous-problèmes plus simples. Cependant, l'analyse de la complexité des algorithmes récursifs peut être plus compliquée par rapport aux algorithmes itératifs. Les principaux aspects à considérer lors de l'analyse des algorithmes récursifs incluent la complexité temporelle et spatiale.

Ces évaluations indiquent combien de temps et de mémoire sont nécessaires pour exécuter l'algorithme en fonction de la taille des données d'entrée. L'analyse de la complexité des algorithmes récursifs implique souvent la construction et la résolution d'équations récurrentes décrivant le comportement de l'algorithme.

Complexité temporelle des algorithmes récursifs :

La complexité temporelle des algorithmes récursifs est souvent analysée en utilisant des relations récurrentes qui décrivent le temps d'exécution de l'algorithme en fonction du temps d'exécution de ses appels récursifs.

Équation récurrente :

L'équation récurrente est une équation qui exprime la complexité temporelle de l'algorithme par rapport à sa complexité temporelle pour des tailles d'entrée plus petites. Elle aide à décrire les coûts temporels nécessaires à l'exécution de l'algorithme récursif.

Exemples :

• T(n) = T(n − 1) + O(1)
• T(n) = 2T(2n) + O(n)

5.2 Exemples de problèmes avec des algorithmes récursifs.

Exemple 1 : Factorielle d'un nombre

Considérons un algorithme pour calculer la factorielle d'un nombre n :

def factorial(n):
    if n == 0:

        return 1

    else:

        return n * factorial(n - 1)
        

L'équation récurrente pour cet algorithme peut être écrite comme :

T(n) = T(n − 1) + O(1)

La solution à cette équation donne :

T(n) = O(n)

Ainsi, la complexité temporelle de l'algorithme de la factorielle est O(n).

Exemple 2 : Tri rapide

Considérons l'algorithme du tri rapide :

def quicksort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]

    left = [x for x in arr if x < pivot]

    middle = [x for x in arr if x == pivot]

    right = [x for x in arr if x > pivot]

    return quicksort(left) + middle + quicksort(right)
        

L'équation récurrente pour cet algorithme dans le cas moyen :

• T(n) = 2 * T(n / 2) + O(n)

La solution à cette équation en utilisant le Master Theorem donne

• T(n) = O(n * log(n))

5.3 Complexité spatiale des algorithmes récursifs

La complexité spatiale des algorithmes récursifs est déterminée par la somme de la mémoire utilisée pour stocker les variables et la mémoire utilisée pour la pile d'appels. Dans les algorithmes profondément récursifs, une quantité significative de mémoire peut être utilisée pour stocker le contexte des appels.

Exemple : Fibonacci

Considérons l'algorithme pour calculer les nombres de Fibonacci :

def fibonacci(n):
    if n <= 1:

        return n

    else:

        return fibonacci(n - 1) + fibonacci(n - 2)
        

L'équation récurrente pour la complexité temporelle :

• T(n) = T(n − 1) + T(n − 2) + O(1)

La solution à cette équation donne :

• T(n) = O(2n)

La complexité spatiale est déterminée par la profondeur maximale des appels récursifs, qui dans ce cas est O(n).

5.4 Méthodes d'analyse de la complexité des algorithmes récursifs

Méthodes d'analyse de la complexité des algorithmes récursifs

1. Méthode de substitution :
• Utilisée pour supposer la forme de la solution et prouver par induction.
• o Exemple : Substitution pour résoudre des équations récurrentes.
2. 2. Méthode de l'arbre de récursion :
   • Visualisation des appels récursifs sous forme d'arbre, où chaque nœud représente un appel de fonction.
   • Exemple : Tri rapide avec appels récursifs.
3. Méthode du maître :
   • Modèle pour analyser les équations récurrentes du type : T(n) = a * T(n / b) + f(n)
   • Exemple : Tri rapide.

L'analyse de la complexité des algorithmes récursifs nécessite de prendre en compte à la fois la complexité temporelle et spatiale. Comprendre les relations récurrentes et appliquer des méthodes d'analyse telles que la substitution, la méthode de l'arbre de récursion et la méthode du maître aident à évaluer précisément les performances des algorithmes récursifs.