01f Fiche méthode - Rappels d'algorithmique

📌 Qu’est-ce qu’un algorithme ?

Un algorithme est une suite finie et non ambiguë d’instructions permettant de résoudre un problème.

💻 En informatique, un bon algorithme doit :

• ✅ Se terminer (finitude)
• ✅ Donner le bon résultat (correction)
• ✅ Être performant (en temps et en mémoire)

---

⚙️ Critères à vérifier

• 🔁 Finitude : il doit s’arrêter après un certain nombre d’étapes.
• 🎯 Correction : le résultat produit doit être juste.
• ⏱️ Performance : il faut évaluer le temps de calcul et l’espace mémoire.

⚠️ Souvent, plus on veut aller vite, plus on consomme de mémoire… et inversement !

🎯 En NSI, on se concentre surtout sur la complexité algorithmique (la durée estimée du calcul).

---

📈 La complexité algorithmique

Elle mesure l’évolution du temps d’exécution en fonction du nombre d’éléments à traiter (N).

---

🔹 Complexité constante — O(1)

➡️ Le temps d’exécution ne dépend pas de la taille des données.

📌 Exemple : accéder à un élément d’une liste par son indice.
🧠 Ultra performant.

---

🔹 Complexité logarithmique — O(log N)

➡️ Le nombre d’étapes augmente lentement quand N augmente.

📌 Exemple : recherche dichotomique, parcours d’arbre binaire
⚡ Très rapide !

---

🔹 Complexité linéaire — O(N)

➡️ Le temps augmente proportionnellement à N.

📌 Exemple : parcourir une liste pour chercher une valeur.
✅ Rapide mais pas optimal.

---

🔹 Complexité quasi-linéaire — O(N log N)

➡️ Combinaison d’un tri divisé + parcours séquentiel.

📌 Exemple : tri rapide (quicksort)
👍 Très efficace.

---

🔹 Complexité polynomiale — O(N²), O(N³), …

➡️ Le temps explose si N devient grand.

📌 Exemple : tri par sélection, double boucle imbriquée
🚫 Acceptable uniquement pour de petites tailles.

---

🔹 Complexité exponentielle / factorielle — O(\(2^N\)), O(N!)

➡️ Le temps double ou plus à chaque ajout de données !

📌 Exemple : voyageur de commerce, résolution naïve de Sudoku, IA, etc.
🛑 Non calculable pour N > 20

---

⏱️ Ordres de grandeur : même avec 1 milliard d’opérations par seconde, certains problèmes sont intraitables dès qu’ils dépassent 20 ou 30 éléments…

---

🔁 Terminaison d’un algorithme : variant de boucle

Un variant de boucle est une valeur entière qui diminue à chaque tour de boucle.
➡️ Cela permet de garantir que la boucle va s’arrêter.

---

Exemple – Plus petite puissance de 2

Fonction : plusPetitePuissance(n)
Objectif : retourner la plus petite puissance de 2 ≥ n

📋 Texte

Début
    p ← 1
    TantQue p < n faire
        p ← 2 × p
Fin

🔍 On pose f(p) = n - p

• f(p) est entier positif
• À chaque tour : p augmente donc f(p) diminue
• Quand p ≥ n, on sort

✅ f(p) est un variant de boucle → l’algorithme se termine.

---

✅ Correction d’un algorithme : invariant de boucle

Un invariant de boucle est une propriété :

• vraie avant la boucle,
• conservée à chaque itération,
• donc vraie à la fin.

C’est ce qui permet de garantir la justesse d’un algorithme.

---

Exemple – Calcul de 2ⁿ

Fonction : calculPuissanceDeux(n) Objectif : retourner \(2^n\)

📋 Texte

Début
    p ← 1
    Pour k de 1 à n faire
        p ← 2 × p
Fin

🧠 Invariant : « p est une puissance de 2 »

• Avant la boucle : p = 1 = 2⁰
• Si p = 2ᵏ, alors p ← 2 × p = 2ᵏ × 2 = 2ᵏ⁺¹
• À la fin : on a fait n tours → p = 2ⁿ

✅ La propriété est conservée → l’algorithme est correct.

---