NSIChapitre 7

Algorithmique

L'essentiel en 30 secondes

L'algorithmique mesure l'efficacité avec la notation $O$ : $O(1) < O(\\log n) < O(n) < O(n \\log n) < O(n^2) < O(2^n)$. Tris au programme : sélection (toujours $O(n^2)$, cherche le min), insertion ($O(n^2)$ pire / $O(n)$ meilleur, insère à sa place). Recherche dichotomique : $O(\\log n)$ mais tableau TRIÉ obligatoire. kNN : classer un élément par vote majoritaire de ses k voisins les plus proches. Prouver un algo : invariant (correction) + variant (terminaison).

Les notions à connaître

Complexité temporelle: Estimation du nombre d'opérations en fonction de la taille n des données. Notation O (grand O) : donne le pire cas. Permet de comparer les algorithmes indépendamment de la machine.
Complexité spatiale: Estimation de la mémoire utilisée en fonction de n. Un algorithme 'en place' utilise $O(1)$ mémoire supplémentaire (modifie le tableau directement).
Tri par sélection: À chaque étape i, chercher le minimum du sous-tableau non trié [i..n-1] et l'échanger avec t[i]. Complexité : TOUJOURS $O(n^2)$ (meilleur = pire). En place. Non stable.
Tri par insertion: Insérer chaque élément à sa place dans la partie déjà triée (comme un jeu de cartes). $O(n^2)$ au pire, $O(n)$ au meilleur (tableau déjà trié). En place. Stable.
Recherche séquentielle (linéaire): Parcourir le tableau élément par élément jusqu'à trouver la valeur ou atteindre la fin. Complexité $O(n)$ . Fonctionne sur tout tableau (trié ou non).
Recherche dichotomique: Diviser par 2 l'espace de recherche à chaque étape : comparer avec le milieu, éliminer une moitié. Requiert un tableau TRIÉ. Complexité $O(\log n)$ .
k plus proches voisins (kNN): Algorithme de classification : calculer la distance à tous les points, garder les k plus proches, voter à la majorité. Complexité $O(n \times d)$ avec d dimensions. k impair pour éviter les égalités.
Algorithme glouton: Fait le choix localement optimal à chaque étape, sans revenir en arrière. Rapide mais ne donne pas toujours la solution globalement optimale. Ex : rendu de monnaie avec système canonique.

Les erreurs à éviter en nsi

Appliquer la recherche dichotomique sur un tableau non trié
Vérifier TOUJOURS que le tableau est trié avant d'utiliser la dichotomie. Sinon, le résultat est faux.
Erreur de borne dans la dichotomie : utiliser g < d au lieu de g <= d
La condition est g <= d (avec <=). Sinon, on peut rater l'élément quand g == d (intervalle de taille 1).
Confondre complexité $O(n)$ et $O(n^2)$ : croire qu'une double boucle est en $O(n)$
Deux boucles imbriquées de taille $n \to$ $O(n^2)$ . Compte le nombre total d'itérations.
Oublier que le tri par insertion est meilleur que la sélection sur des données quasi-triées
Insertion : $O(n)$ au meilleur. Sélection : TOUJOURS $O(n^2)$ . Pour des données presque triées, insertion est bien meilleur.
Utiliser m = (g + d) / 2 au lieu de (g + d) // 2
La division entière // est obligatoire pour obtenir un indice entier. / donne un float en Python.

Sais-tu répondre à ces questions ?

Les corrigés détaillés sont dans le quiz du chapitre.

Quelle est la complexité en temps de la recherche séquentielle dans une liste non triée de n éléments ?
Qu'est-ce qu'un algorithme glouton ?
Combien de comparaisons au maximum faut-il pour trouver un élément par recherche dichotomique dans une liste triée de 1000 éléments ?
Qu'affiche le code suivant (tri par sélection) ? def tr $i_s$ election(lst): for i in range(len(lst)): m = i for j in range(i + 1, len(lst)): if lst[j] < lst[m]: m = j lst[i], lst[m] = lst[m], lst[i] return lst print(tr $i_s$ election([3, 1, 4, 1]))
Quelle est la complexité en temps du tri par insertion dans le pire cas ?

Accède à la fiche complète

Crée ton compte gratuit pour lire la fiche en entier et accéder à 7 000+ contenus de révision.

Créer un compte gratuit Se connecter