Notion de complexité algorithmique en 1ère
Notion de complexité algorithmique, c'est une notion de nsi du chapitre « Algorithmique et programmation », au programme de 1ère. Voici le cours, un exemple et de quoi t'entraîner.
Notion de complexité algorithmique : le cours
La complexité d'un algorithme mesure comment son temps d'exécution augmente avec la taille des données. On l'exprime souvent en nombre d'opérations nécessaires dans le pire des cas, en fonction de la taille n des données (par exemple n, n², ou log n).
Exemple
Sur un tableau trié de 1 000 éléments, une recherche séquentielle peut nécessiter jusqu'à 1 000 comparaisons, alors qu'une recherche dichotomique n'en demande qu'environ 10 (car $2^{10} = 1024$).
À retenir
Un algorithme en log n (dichotomie) passe à l'échelle bien mieux qu'un algorithme en n (parcours séquentiel) quand les données deviennent très nombreuses.
S'entraîner sur notion de complexité algorithmique
Fais l'exercice, puis demande au tuteur de te corriger pas à pas.
Exercice 1
Écris une fonction qui recherche un nombre dans une liste triée en utilisant la recherche dichotomique. Teste-la avec assert pour vérifier qu'elle retourne l'index correct ou -1 si le nombre n'existe pas.
Corrige cet exercice avec le tuteur →Exercice 2
Crée une fonction tri_par_insertion(liste) qui trie une liste en utilisant le tri par insertion. Utilise des assertions pour vérifier que la liste retournée est bien triée et contient les mêmes éléments.
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Algorithmique et programmation (NSI 1ère).