Qu'est-ce que la complexité algorithmique en NSI
La complexité algorithmique mesure l'efficacité d'un algorithme en termes de temps d'exécution et d'espace mémoire utilisé. En NSI, on se concentre principalement sur la complexité temporelle exprimée en notation O (« grand O »). Les complexités les plus courantes sont : O(1) temps constant (accès à un élément de liste par index), O(log n) logarithmique (recherche dichotomique), O(n) linéaire (parcours d'une liste), O(n log n) quasi-linéaire (tri fusion, tri rapide en moyenne), O(n²) quadratique (tri par sélection, tri par insertion), O(2^n) exponentielle (certains algorithmes récursifs naïfs comme Fibonacci). Plus la complexité est faible, plus l'algorithme est efficace pour de grandes entrées. Par exemple, trier 1 million d'éléments prend environ 20 millions d'opérations en O(n log n) mais 1 000 milliards en O(n²). Au bac, vous devez savoir déterminer la complexité d'un algorithme donné et comparer deux algorithmes résolvant le même problème. Sur NSI-Lycée, nous proposons des exercices de calcul de complexité avec des animations montrant la différence de performance entre algorithmes. Consultez revisemaths.fr pour les fonctions logarithmiques et exponentielles, et calculemoi.fr pour les ordres de grandeur.
