Rechercher une valeur dans une liste et dans un dictionnaire
- Fiche de cours
- Quiz et exercices
- Vidéos et podcasts
Comprendre que la recherche d’une valeur dans une liste et dans un dictionnaire est différente.
- Dans une liste, on parcourt tous les éléments pour chercher une valeur. La complexité temporelle associée à l’utilisation d’une liste dans un algorithme vaut O(n).
- Dans un dictionnaire, on accède directement
à une valeur à partir de la clé
associée.
La complexité temporelle associée à l’utilisation d’un dictionnaire dans un algorithme vaut O(1). - L’utilisation d’un algorithme avec un dictionnaire permet donc un gain en termes d’efficacité par rapport à l’utilisation d’une liste.
Structures de données : interfaçage, implémentation
Chaque élément est repéré par un rang que l’on nomme indice.
Ce type de structure de données est linéaire, car on accède toujours à un élément en partant du premier. Il y a donc une fonction successeur qui permet d’accéder à l’élément suivant. Chaque élément de la liste est ainsi accessible.
Une structure est qualifiée de linéaire lorsqu’on peut avoir une fonction successeur qui associe à chacun de ses éléments (sauf pour le dernier) un unique autre élément de la même structure (l'élément suivant).
On doit de plus pouvoir parcourir l'intégralité de la structure à l'aide de cette fonction successeur sans passer deux fois par le même élément.
La variable Course référence une liste qui contient une liste de courses de 3 éléments.
Course=["tomates", "salade", "beurre"]
- La liste est native dans Python puisqu’elle est déjà implémentée (définie).
- Le premier élément de la liste est appelé l’en-tête.
La liste est une représentation qui permet les opérations suivantes (primitives).
- Créer une liste vide : creer_liste()
- Ajouter x en en-tête à la liste L : entete(x,L)
- Supprimer l’en-tête (premier élément) de la liste L : suppr(L)
- Obtenir l’en-tête (premier élément) de la liste L : entete(L)
- Obtenir la queue (dernier élément) de la liste L : queue(L)
- Tester si la liste L est vide : vide(L)
Autre formulation : Un dictionnaire est une collection non numérotée de couples de valeurs clé:valeur, avec la clé qui est un objet non modifiable et la valeur qui est l’élément associé à cette clé.
Un dictionnaire est délimité par des {}.
Ce type de structure de données est non linéaire, car il faut une clé pour accéder à un élément d’un dictionnaire.
La variable informaticiens référence un dictionnaire qui contient le nom de deux informaticiens et l'année de naissance de chacun de ces informaticiens.
informaticiens={"Cynthia Dwork":1958,"Marvin Minsky":1927}
Dans ce dictionnaire, Cynthia Dwork et Marvin Minsky sont des clés, auxquelles sont associées les valeurs 1958 et 1927.Le dictionnaire est une structure de données native dans Python puisqu’elle est déjà implémentée (définie).
Le dictionnaire est une représentation qui permet les opérations suivantes (primitives).
- Créer un dictionnaire : dict()
- Ajouter une nouvelle valeur à une nouvelle clé : nom_dico['clé']='valeur'
- Supprimer une clé : del nom_dico['clé']
- Rechercher une valeur à l’aide de la clé associée à cette valeur : nom_dico[‘clé’]
À chaque étape, on compare la valeur de l’élément de la liste à la valeur recherchée.
Si la liste a une taille n, il y a au pire des cas un nombre d’opérations de même ordre que n : la complexité temporelle (temps d’exécution) associée à l’utilisation d’une liste vaut donc O(n).
Voici l’exécution d’un programme avec Python Tutor, pour chercher un élément dans la liste [1,5,7,55,13,333].
La ligne 2 demande à l’utilisateur d’indiquer l’élément à chercher dans la liste. On obtient à la fin l’élément recherché sur la première ligne, et l’indice où l’élément se trouve sur la seconde ligne. Cette ligne est vide si l’élément n’est pas présent dans la liste.
L’utilisation de la clé fait partie des opérations (primitives) du dictionnaire, on a donc un nombre d'opérations qui est indépendant de la taille du dictionnaire à traiter : la complexité temporelle (temps d’exécution) associée à l’utilisation d’un dictionnaire vaut donc O(1).
Voici l’exécution d’un programme avec Python Tutor, pour chercher la lettre « d » dans le dictionnaire :
dict={"a":1,"b":23,"c":'5',"d":899}.
On obtient yes, ce qui signifie que la lettre « d » est bien présente dans le dictionnaire dict.
La complexité temporelle associée à l’utilisation d’un dictionnaire est inférieure à la complexité temporelle associée à l’utilisation d’une liste (O(1) < O(n)).
Évalue ce cours !
Des quiz et exercices pour mieux assimiler sa leçon
La plateforme de soutien scolaire en ligne myMaxicours propose des quiz et exercices en accompagnement de chaque fiche de cours. Les exercices permettent de vérifier si la leçon est bien comprise ou s’il reste encore des notions à revoir.
Des exercices variés pour ne pas s’ennuyer
Les exercices se déclinent sous toutes leurs formes sur myMaxicours ! Selon la matière et la classe étudiées, retrouvez des dictées, des mots à relier ou encore des phrases à compléter, mais aussi des textes à trous et bien d’autres formats !
Dans les classes de primaire, l’accent est mis sur des exercices illustrés très ludiques pour motiver les plus jeunes.
Des quiz pour une évaluation en direct
Les quiz et exercices permettent d’avoir un retour immédiat sur la bonne compréhension du cours. Une fois toutes les réponses communiquées, le résultat s’affiche à l’écran et permet à l’élève de se situer immédiatement.
myMaxicours offre des solutions efficaces de révision grâce aux fiches de cours et aux exercices associés. L’élève se rassure pour le prochain examen en testant ses connaissances au préalable.
Des vidéos et des podcasts pour apprendre différemment
Certains élèves ont une mémoire visuelle quand d’autres ont plutôt une mémoire auditive. myMaxicours s’adapte à tous les enfants et adolescents pour leur proposer un apprentissage serein et efficace.
Découvrez de nombreuses vidéos et podcasts en complément des fiches de cours et des exercices pour une année scolaire au top !
Des podcasts pour les révisions
La plateforme de soutien scolaire en ligne myMaxicours propose des podcasts de révision pour toutes les classes à examen : troisième, première et terminale.
Les ados peuvent écouter les différents cours afin de mieux les mémoriser en préparation de leurs examens. Des fiches de cours de différentes matières sont disponibles en podcasts ainsi qu’une préparation au grand oral avec de nombreux conseils pratiques.
Des vidéos de cours pour comprendre en image
Des vidéos de cours illustrent les notions principales à retenir et complètent les fiches de cours. De quoi réviser sa prochaine évaluation ou son prochain examen en toute confiance !
Fiches de cours les plus recherchées
NSI
Comprendre la structure hiérarchique des arbres binaires
NSI
Étudier et implémenter un arbre binaire
NSI
Utiliser des arbres binaires de recherche
NSI
Comprendre la structure des graphes
NSI
Implémenter un graphe
NSI
Passer d'une représentation d'un graphe à une autre
NSI
Comprendre le modèle relationnel d'une base de données
NSI
Utiliser l'algèbre relationnel dans une base de données relationnelle
NSI
Repérer des anomalies dans une base de données relationnelle
NSI
Introduire la notion de système de gestion de base de données relationnelle
Fermer
Accédez gratuitement à
