Algorithmique Avancée: Tri, Recherche et Complexité

Correction :

La complexité algorithmique est une mesure de l'efficacité d'un algorithme, généralement en termes de temps d'exécution (complexité temporelle) et d'espace mémoire utilisé (complexité spatiale), en fonction de la taille de l'entrée $N$. Elle permet de prédire comment l'algorithme va se comporter lorsque la taille des données augmente.

Elle est importante car elle permet de :

• Comparer des algorithmes : Choisir le plus efficace parmi plusieurs solutions pour le même problème.
• Prévoir les performances : Estimer le temps que prendra un algorithme sur de grandes quantités de données.
• Optimiser les ressources : Concevoir des algorithmes qui consomment moins de temps ou de mémoire.

Exemple : Imagine que tu as une base de données de millions d'utilisateurs et que tu veux rechercher un utilisateur spécifique. Un algorithme de recherche linéaire (qui parcourt tous les utilisateurs un par un) serait "lent" ($O(N)$), tandis qu'un algorithme de recherche dichotomique sur une liste triée (qui divise le problème en deux à chaque étape) serait "rapide" ($O(\log N)$). Sur des millions d'éléments, la différence de temps d'exécution serait spectaculaire, transformant une attente de plusieurs minutes en quelques fractions de seconde.

Point méthode : La complexité s'exprime souvent avec la notation Grand O ($O(N)$), qui décrit le comportement asymptotique de l'algorithme pour de grandes valeurs de $N$.

Correction :

Le tri par sélection cherche le minimum dans la partie non triée du tableau et le place au début de cette partie.

Tableau initial : [64, 25, 12, 22, 11]

Passage 1 (i=0) :
 Minimum dans [64, 25, 12, 22, 11] est 11 (à l'index 4).
 Échange 64 et 11.
 État du tableau : [11, 25, 12, 22, 64] (11 est maintenant trié)

Passage 2 (i=1) :
 Minimum dans [25, 12, 22, 64] est 12 (à l'index 2).
 Échange 25 et 12.
 État du tableau : [11, 12, 25, 22, 64] (11, 12 sont triés)

Passage 3 (i=2) :
 Minimum dans [25, 22, 64] est 22 (à l'index 3).
 Échange 25 et 22.
 État du tableau : [11, 12, 22, 25, 64] (11, 12, 22 sont triés)

Passage 4 (i=3) :
 Minimum dans [25, 64] est 25 (à l'index 3).
 Échange 25 et 25 (pas de changement).
 État du tableau : [11, 12, 22, 25, 64] (11, 12, 22, 25 sont triés)

Le dernier élément est automatiquement trié.

Astuce : Le tri par sélection est simple à comprendre : à chaque étape, tu trouves le plus petit élément restant et tu le mets à sa place correcte.

Correction :

Le tri à bulles compare les éléments adjacents et les échange s'ils sont dans le mauvais ordre. Les éléments les plus grands "flottent" vers la fin.

Tableau initial : [5, 1, 4, 2, 8]

Passage 1 :
 (5, 1) -> [1, 5, 4, 2, 8]
 (5, 4) -> [1, 4, 5, 2, 8]
 (5, 2) -> [1, 4, 2, 5, 8]
 (5, 8) -> [1, 4, 2, 5, 8]
 État après Passage 1 : [1, 4, 2, 5, 8] (8 est à sa place)

Passage 2 :
 (1, 4) -> [1, 4, 2, 5, 8]
 (4, 2) -> [1, 2, 4, 5, 8]
 (4, 5) -> [1, 2, 4, 5, 8]
 État après Passage 2 : [1, 2, 4, 5, 8] (5 et 8 sont à leur place)

Passage 3 :
 (1, 2) -> [1, 2, 4, 5, 8]
 (2, 4) -> [1, 2, 4, 5, 8]
 État après Passage 3 : [1, 2, 4, 5, 8] (4, 5, 8 sont à leur place)

Passage 4 :
 (1, 2) -> [1, 2, 4, 5, 8]
 État après Passage 4 : [1, 2, 4, 5, 8] (2, 4, 5, 8 sont à leur place)

Astuce : Le tri à bulles est souvent le premier algorithme de tri enseigné. Il est simple mais peu efficace pour de grands tableaux.

Correction :

La recherche linéaire parcourt le tableau élément par élément jusqu'à trouver la valeur ou atteindre la fin.

1. Recherche de 42 :
   • 15 != 42
   • 8 != 42
   • 23 != 42
   • 42 == 42 (Trouvé !)

   Il faut 4 comparaisons pour trouver 42.

2. Recherche de 99 :

   L'algorithme devrait comparer 99 avec chaque élément du tableau jusqu'à la fin.

   15, 8, 23, 42, 10, 5, 17

   Il y a 7 éléments. Donc, il faudrait 7 comparaisons avant de conclure que 99 n'est pas dans le tableau.

3. Complexité temporelle dans le pire des cas :

   Dans le pire des cas (l'élément n'est pas trouvé ou se trouve à la dernière position), l'algorithme doit parcourir tous les $N$ éléments du tableau.

   $$O(N)$$

   La complexité est $O(N)$ (linéaire).

Astuce : La recherche linéaire fonctionne sur des tableaux non triés, mais elle est moins efficace que la recherche dichotomique sur de grands tableaux triés.

Correction :

La recherche dichotomique (ou binaire) ne fonctionne que sur un tableau trié. Elle divise le problème en deux à chaque étape.

Tableau : [10, 20, 30, 40, 50, 60, 70, 80, 90] (taille N=9)
Recherche de : 70

Itération 1 :
 début = 0, fin = 8
 milieu = (0 + 8) / 2 = 4
 valeur_milieu = tableau[4] = 50
 70 > 50, donc on cherche dans la moitié supérieure.
 nouveau début = milieu + 1 = 5.
 État : [10, 20, 30, 40, | 50 |, 60, 70, 80, 90]

Itération 2 :
 début = 5, fin = 8
 milieu = (5 + 8) / 2 = 6 (arrondi inférieur)
 valeur_milieu = tableau[6] = 70
 70 == 70 (Trouvé !)

Point méthode : L'efficacité de la recherche dichotomique repose sur le fait de diviser l'espace de recherche par deux à chaque étape, ce qui conduit à une complexité logarithmique.

Correction :

1. POUR i DE 1 À N FAIRE
    AFFICHER "Bonjour"
   FIN POUR
    

   La boucle s'exécute $N$ fois. L'opération AFFICHER "Bonjour" est considérée comme une opération constante ($O(1)$). Donc, le total est $N \times O(1)$.

   Complexité : $O(N)$ (linéaire)

2. POUR i DE 1 À N FAIRE
    POUR j DE 1 À N FAIRE
    AFFICHER "Salut"
    FIN POUR
   FIN POUR
    

   La boucle externe s'exécute $N$ fois. Pour chaque itération de la boucle externe, la boucle interne s'exécute également $N$ fois. Donc, le nombre total d'opérations est $N \times N = N^2$.

   Complexité : $O(N^2)$ (quadratique)

3. POUR i DE 1 À N FAIRE
    POUR j DE 1 À i FAIRE
    AFFICHER "Hello"
    FIN POUR
   FIN POUR
    

   La boucle externe s'exécute $N$ fois. La boucle interne s'exécute $i$ fois pour chaque $i$. Le nombre total d'opérations est $1 + 2 + 3 + . + N$. C'est la somme des $N$ premiers entiers, qui est donnée par la formule $N \times (N+1) / 2$. Cette expression est de l'ordre de $N^2/2 + N/2$, ce qui est équivalent à $O(N^2)$ car les termes constants et les termes d'ordre inférieur sont ignorés.

   Complexité : $O(N^2)$ (quadratique)

Point méthode : Pour les boucles imbriquées, la complexité est généralement le produit des complexités des boucles individuelles. Fais attention si les bornes des boucles dépendent les unes des autres.

Correction :

1. Tableau non trié :

   La seule méthode applicable est la recherche linéaire.

   Sa complexité dans le pire des cas est $O(N)$. Pour $N = 10^6$, cela signifie jusqu'à $10^6$ comparaisons.

2. Tableau trié :

   La méthode la plus efficace est la recherche dichotomique (ou binaire).

   Sa complexité dans le pire des cas est $O(\log N)$.

   Pour $N = 10^6$, le nombre maximal de comparaisons est approximativement $\log_2(10^6)$.

   $\log_2(10^6) \approx \log_2((2^{10})^2) = \log_2(2^{20}) = 20$.

   En réalité, c'est $\lfloor\log_2 N\rfloor + 1$. Pour $N=10^6$, $2^{19} = 524288$ et $2^{20} = 1048576$. Donc, il faudrait environ $20$ comparaisons.

Astuce : La différence entre $10^6$ et 20 est colossale ! Cela illustre parfaitement l'importance de choisir le bon algorithme et de tirer parti des propriétés des données (comme être triées).

Correction :

Le tri par insertion construit le tableau trié un élément à la fois. Chaque nouvel élément est inséré à sa place correcte dans la sous-liste déjà triée.

Tableau initial : [12, 11, 13, 5, 6]

On considère le premier élément (12) déjà trié.

Passage 1 (insérer 11) :
 Comparer 11 avec 12. 11 < 12. Décaler 12.
 Insérer 11.
 État du tableau : [11, 12, 13, 5, 6] (Sous-liste triée : [11, 12])

Passage 2 (insérer 13) :
 Comparer 13 avec 12. 13 > 12. Pas de décalage.
 Comparer 13 avec 11. 13 > 11. Pas de décalage.
 Insérer 13 à sa place.
 État du tableau : [11, 12, 13, 5, 6] (Sous-liste triée : [11, 12, 13])

Passage 3 (insérer 5) :
 Comparer 5 avec 13. 5 < 13. Décaler 13.
 Comparer 5 avec 12. 5 < 12. Décaler 12.
 Comparer 5 avec 11. 5 < 11. Décaler 11.
 Insérer 5.
 État du tableau : [5, 11, 12, 13, 6] (Sous-liste triée : [5, 11, 12, 13])

Passage 4 (insérer 6) :
 Comparer 6 avec 13. 6 < 13. Décaler 13.
 Comparer 6 avec 12. 6 < 12. Décaler 12.
 Comparer 6 avec 11. 6 < 11. Décaler 11.
 Comparer 6 avec 5. 6 > 5. Insérer 6 après 5.
 État du tableau : [5, 6, 11, 12, 13] (Sous-liste triée : [5, 6, 11, 12, 13])

Point méthode : Le tri par insertion est efficace pour de petits ensembles de données ou des tableaux presque triés. Sa complexité est $O(N^2)$ dans le pire des cas, mais $O(N)$ dans le meilleur des cas (tableau déjà trié).

Correction :

Analysons le nombre d'opérations pour factorielle(N) :

• Pour factorielle(0) : 1 appel, 0 multiplication.
• Pour factorielle(1) : appelle factorielle(0), puis 1 multiplication. Total 2 appels, 1 multiplication.
• Pour factorielle(2) : appelle factorielle(1) (qui lui-même appelle factorielle(0)), puis 1 multiplication. Total 3 appels, 2 multiplications.
• Pour factorielle(N) : appelle factorielle(N-1), qui appelle factorielle(N-2) . jusqu'à factorielle(0). Il y aura $N$ appels récursifs + l'appel initial, soit $N+1$ appels de fonction. Il y aura également $N$ multiplications.

Le nombre d'opérations (multiplications ou appels récursifs) est directement proportionnel à $N$.

Justification : Le nombre d'appels récursifs et de multiplications croît linéairement avec la valeur de $N$. Chaque appel effectue un travail constant (une comparaison, une multiplication, un retour).

Point méthode : Pour les fonctions récursives, le nombre d'appels de fonction est un bon indicateur de la complexité temporelle. Fais attention aux fonctions récursives qui créent un arbre d'appels (comme Fibonacci sans mémoïsation), leur complexité peut être exponentielle.

Correction :

1. Principe général du tri fusion :

   Le tri fusion est un algorithme récursif de tri basé sur le paradigme "diviser pour régner".

   • Diviser : Il divise le tableau (ou la liste) non trié en deux moitiés jusqu'à ce que chaque sous-tableau contienne un seul élément (qui est par définition trié).
   • Régner (Fusionner) : Ensuite, il fusionne (merge) de manière répétée les sous-tableaux triés pour produire de nouveaux sous-tableaux triés, jusqu'à ce qu'il ne reste qu'un seul tableau trié. La clé est la phase de fusion, qui prend deux listes triées et les combine en une seule liste triée en comparant les éléments de manière efficace.
2. Complexité temporelle :

   La complexité temporelle du tri fusion dans le pire des cas est $O(N \log N)$.

   Pourquoi :

   • Division : Le processus de division du tableau en deux à chaque étape prend $\log N$ étapes (comme pour un arbre binaire de hauteur $\log N$).
   • Fusion : À chaque niveau de fusion, l'opération de fusion de tous les sous-tableaux triés prend un temps linéaire, $O(N)$, car chaque élément doit être examiné et placé une fois.

   Comme il y a $\log N$ niveaux de divisions/fusions, et que chaque niveau de fusion coûte $O(N)$, la complexité totale est le produit de ces deux facteurs.

   $$O(N \log N)$$

Astuce : Le tri fusion est un exemple parfait d'algorithme "diviser pour régner" et il est stable (conserve l'ordre relatif des éléments égaux), contrairement à d'autres tris $O(N \log N)$ comme le tri rapide (Quick Sort).