Optimisation & Suite de Fibonacci

0. Méthodologie : Comment compter les appels ?

Outil d'analyse

Pour déterminer la complexité d'un algorithme récursif, on ne devine pas. On suit une méthode stricte :

1

Traduire le Code en Récurrence
On note $ A(n) $ le nombre d'appels. On lit le code :

Pour chaque appel récursif, on ajoute un terme $ A(...) $.
On ajoute $ +1 $ pour l'appel courant.

Exemple : Si le code appelle une fois la fonction avec $ n/2 $, on écrit : $ A(n) = 1 + A(n/2) $.

2

Résoudre la Récurrence
On cherche quelle fonction mathématique correspond à l'équation :

$ A(n) = A(n-1) + ... $ $\to$ Souvent Linéaire $ O(n) $
$ A(n) = A(n/2) + ... $ $\to$ Souvent Logarithmique $ O(\log n) $
$ A(n) = A(n-1) + A(n-2) $ $\to$ Souvent Exponentiel $ O(\phi^n) $

1. Contexte Historique (1202)

Introduit par Léonard de Pise (Fibonacci) dans le Livre de l’abaque. L'objectif initial était d'étudier l'évolution d'une population de lapins.

Modèle de croissance :

$ x $ : couple de lapereaux (ne se reproduisent pas encore)
$ X $ : couple de lapins adultes (se reproduisent)

Relation de récurrence : $ F(n) = F(n-1) + F(n-2) $ pour $ n \ge 2 $

Mois (n)	Lapereaux (x)	Adultes (X)	Total F(n)
1	1	0	1
2	0	1	1
3	1	1	2
4	1	2	3
5	2	3	5

2. Premier Algorithme : Formule de Binet

O(1) Mathématique

On résout l'équation caractéristique $ r^2 - r - 1 = 0 $. Les racines incluent le nombre d'or $ \phi $.

$$ F(n) = \frac{1}{\sqrt{5}} \left[ \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right] $$

Approximation : $ F(n) \sim \frac{1}{\sqrt{5}} \phi^n $

⚠️ Bien que mathématiquement directe, cette méthode pose des problèmes de précision flottante sur ordinateur pour les grands nombres.

3. Deuxième Algorithme : Récursif Naïf

Exponentiel

Fonction F(n)
    Si n <= 1 Alors Retourne n 
    Sinon Retourne F(n-1) + F(n-2) 
Fin Si

Analyse : Le nombre d'additions est $ P(n) = F(n+1) - 1 $.
La complexité explose de manière exponentielle : $ O(\phi^n) $.

4. Troisième Algorithme : Itératif

O(n) Linéaire

Fonction F(n)
    a = 1, b = 0
    Pour i de 1 à n :
        a, b = a + b, a
    Retour b

Complexité : $ P(n) = n $. Simple et efficace pour la plupart des usages standards.

5. Algorithme Dichotomique (Fast Doubling)

O(log n) Logarithmique

On utilise les formules de duplication pour sauter les étapes (méthode "Divide and Conquer").

$$ F(2n) = F(n)^2 + 2F(n)F(n-1) $$ $$ F(2n+1) = F(n)^2 + F(n+1)^2 $$

Implémentation (Fonction G)

La fonction $ G(n) $ retourne le couple $ (F(n), F(n+1)) $.

Fonction G(n) : (entier, entier)
    Si n = 0 Alors Retour (0, 1)

    // Appel récursif sur la moitié
    (p, q) = G((n-1)/2)  
    
    Si n est pair Alors
        Retour (2pq + q², q² + (p+q)²)
    Sinon
        Retour (p² + q², 2pq + q²)
    FinSi

🚀

Performance : $ A(n) = 1 + \log_2(n+1) $.
Pour $ n=1000 $, seulement ~10 appels nécessaires !

6. Exercice d'Application

Analyse

Soit la fonction $ f(n) $ définie par la récurrence :

$$ f(2n) = 2n + 2f(n) $$ $$ f(2n+1) = (2n+1) + f(n) + f(n+1) $$

n	A(n) Appels
1	1
2	3
3	5
4	7

On observe que $ A(n) = 2n - 1 $.
C'est donc une complexité Linéaire.
Pour l'optimiser en logarithmique, il faudrait utiliser la technique du couple (comme Fibonacci).

7. Généralisation : Exponentiation Rapide

O(log n) Logarithmique

Même principe appliqué au calcul de puissance $ x^n $. Propriété clé : $ x^{2n} = (x^n)^2 $.

def e(x, n):
    if n == 0 : return 1        // Arrêt
    val = e(x, n // 2)          // 1 seul appel récursif !
    val = val * val
    if n % 2 == 0 : return val  // n pair
    return val * x              // n impair

Analyse du nombre d'appels

1. Récurrence : $ A(n) = 1 + A(\lfloor n/2 \rfloor) $

2. Résolution : $ A(n) = \lfloor \log_2(n) \rfloor + 2 $

Le +2 provient de l'appel pour $ n=1 $ et de la condition d'arrêt $ n=0 $.