🧱
Tableaux et indicesUne structure de données organise les informations en mémoire pour les manipuler efficacement. Le tableau est la plus simple : des éléments côte à côte, accessibles par un indice entier. En Python, une liste se comporte comme un tableau dynamique. Les indices commencent à 0, donc le dernier élément d'un tableau de n éléments est à l'indice n-1. L'accès direct à un élément par son indice est immédiat, quel que soit l'emplacement.
📢 Rappel
Une variable stocke une seule valeur ; un tableau stocke plusieurs valeurs sous un même nom, repérées par des indices.
💡 À retenir : L'accès à un élément d'un tableau par son indice est direct et rapide.
🥞
LIFO et FIFOUne pile suit le principe LIFO (Last In, First Out) : le dernier élément ajouté est le premier retiré, comme une pile d'assiettes. Une file suit le principe FIFO (First In, First Out) : le premier arrivé est le premier servi, comme une file d'attente. Les opérations principales sont empiler/dépiler pour une pile, enfiler/défiler pour une file. Ces structures sont très utilisées en informatique, par exemple pour gérer l'historique d'un navigateur ou l'impression de documents.
📖 Définition
Pile : structure LIFO où l'on ajoute et retire des éléments uniquement au sommet.
🔍 Exemple
L'historique des pages visitées dans un navigateur fonctionne comme une pile : le bouton retour dépile la dernière page visitée.
⭐ À retenir
Toujours identifier si l'ordre d'utilisation est celui d'arrivée (file) ou inverse (pile).
💡 À retenir : La pile mémorise l'ordre inverse des actions ; la file conserve l'ordre d'arrivée.
🗂️
Clés et valeursUn dictionnaire associe une clé unique à une valeur, comme un annuaire téléphonique associe un nom à un numéro. L'accès à une valeur se fait via sa clé, sans parcourir toute la collection. Un ensemble stocke des éléments uniques, sans ordre et sans doublon. Ces structures permettent des recherches très efficaces grâce à des fonctions de hachage. En Python, on utilise les types dict et set.
📖 Définition
Dictionnaire : collection de couples clé-valeur où chaque clé est unique.
🔍 Exemple
Un carnet de contacts : le nom est la clé, le numéro de téléphone est la valeur.
⭐ À retenir
Utiliser un dictionnaire dès que l'on veut retrouver une information à partir d'un identifiant unique.
💡 À retenir : Avec une clé, l'accès à une valeur est direct, comme chercher un mot dans un dictionnaire papier grâce à l'ordre alphabétique.
⏱️
Notation grand OLa complexité évalue le nombre d'opérations effectuées par un algorithme en fonction de la taille n des données. On utilise la notation grand O pour décrire l'ordre de grandeur dans le pire des cas. Une recherche séquentielle dans un tableau est en O(n) : on peut devoir parcourir tous les éléments. Une recherche dichotomique dans un tableau trié est en O(log₂ n) : on divise l'espace de recherche par deux à chaque étape. Un tri par insertion est en O(n²) car il compare chaque élément à presque tous les précédents.
📢 Rappel
Le logarithme base 2 de n est le nombre de fois où l'on peut diviser n par 2 avant d'atteindre 1.
⭐ À retenir
Un algorithme en O(log n) est plus efficace qu'en O(n) pour de grandes valeurs de n ; O(n²) devient vite très lent.
💡 À retenir : La complexité permet de comparer des algorithmes indépendamment de la machine utilisée.