Algorithmique appliquée | BTS | Mathématiques
Dernière mise à jour : 15 juin 2026
On cherche une valeur dans un tableau de 50 éléments par recherche séquentielle.
1. Combien de comparaisons au maximum (pire cas) ?
2. En moyenne (valeur présente, position quelconque) ?
1. Au pire : 50 comparaisons. 2. En moyenne : environ \(\frac{50}{2}=25\) comparaisons.
Un tableau trié contient 1024 éléments.
Combien de comparaisons au maximum avec une recherche dichotomique ?
Environ \(\log_2(1024)=10\) comparaisons (chaque étape divise la zone de recherche par 2). Bien plus rapide que la recherche séquentielle (1024 au pire).
Applique le tri par sélection (on place le minimum en tête à chaque étape) au tableau \([5,\ 2,\ 4,\ 1]\). Donne les états successifs.
Min = 1 → \([1,\ 2,\ 4,\ 5]\) ; min du reste = 2 (déjà placé) → \([1,2,4,5]\) ; puis 4, puis 5. Tableau trié : \([1,2,4,5]\).
On définit la factorielle par \(f(0)=1\) et \(f(n)=n\times f(n-1)\).
Déroule le calcul de \(f(4)\).
\(f(4)=4\times f(3)=4\times3\times f(2)=4\times3\times2\times f(1)=4\times3\times2\times1\times f(0)=24\).
Un algorithme parcourt un tableau de \(n\) éléments avec deux boucles imbriquées (pour chaque élément, on reparcourt tout le tableau).
1. Combien d'opérations en fonction de \(n\) ? 2. Quelle est sa complexité ?
1. \(n\times n=n^2\) opérations. 2. Complexité \(O(n^2)\) (quadratique) : le temps croît comme le carré de la taille des données.