EazyReviz

L'essentiel en 30 secondes

L'algorithmique, c'est savoir résoudre un problème EFFICACEMENT. La complexité mesure le coût d'un algorithme (en temps ou en espace). Les tris par sélection et par insertion sont en $O(n^2)$ . La recherche dichotomique est en $O(log n)$ mais nécessite un tableau TRIÉ. L'algorithme des $k$ plus proches voisins (kNN) classe un élément selon ses voisins les plus proches.

Notions clés

Complexité temporelle: Estimation du nombre d'opérations en fonction de la taille n des données. Notée O(…) : le pire cas.
Tri par sélection: $À$ chaque étape, on cherche le minimum du $sous-tableau$ non trié et on le place au bon endroit. $O(n^2)$ .
Tri par insertion: On insère chaque élément $à$ sa place dans la partie déjà triée (comme un jeu de cartes). $O(n^2)$ .
Recherche dichotomique: Diviser par 2 l'espace de recherche à chaque étape. Requiert un tableau trié. O(log n).
k plus proches voisins (kNN): Algorithme de classification : on attribue à un élément la classe majoritaire parmi ses k voisins les plus proches.
Invariant de boucle: Propriété vraie avant et après chaque itération d'une boucle. Sert à prouver la correction d'un algorithme.

Formules

Tri par sélection

`def tri_selection(t):\n for i in range(len(t)):\n i_min = i\n for j in range(i+1, len(t)):\n if t[j] < t[i_min]:\n i_min = j\n t[i], t[i_min] = t[i_min], t[i]`

Condition : Complexité $O(n^2)$ dans tous les cas. Tri en place.

Tri par insertion

`def tri_insertion(t):\n for i in range(1, len(t)):\n cle = t[i]\n j = i - 1\n while j >= 0 and t[j] > cle:\n t[j+1] = t[j]\n j -= 1\n t[j+1] = cle`

Condition : $O(n^2)$ au pire cas, $O(n)$ si tableau presque trié. Tri en place, stable.

Recherche dichotomique

`def dicho(t, v):\n g, d = 0, len(t) - 1\n while g <= d:\n m = (g + d) // 2\n if t[m] == v:\n return m\n elif t[m] < v:\n g = m + 1\n else:\n d = m - 1\n return None`

Condition : Complexité O(log n). Le tableau DOIT être trié au préalable.

Complexités à connaître

O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)

Condition : Du plus efficace au moins efficace. n log n = tri optimal (Python sorted).

A retenir

La recherche dichotomique ne fonctionne QUE sur un tableau trié. C'est la condition à vérifier en premier.
Tri par sélection $=$ toujours $O(n^2)$ . Tri par insertion $= O(n)$ au meilleur cas (tableau déjà trié) $\to$ avantage insertion.
Pour kNN, le choix de k et de la distance influencent fortement le résultat. k impair évite les égalités.

Erreurs classiques

Erreur : Appliquer la recherche dichotomique sur un tableau non trié

Correction : Vérifier TOUJOURS que le tableau est trié avant d'utiliser la dichotomie. Sinon, le résultat est faux.

Erreur : Erreur de borne dans la dichotomie : utiliser g < d au lieu de g <= d

Correction : La condition est g <= d (avec <=). Sinon, on peut rater l'élément quand g == d.

Erreur : Confondre complexité $O(n)$ et $O(n^2)$ : croire qu'une double boucle est en $O(n)$

Correction : Deux boucles imbriquées de taille $n \to O(n^2)$ . Compte le nombre total d'opérations.

Astuce méthode