Algorithmique avancée : structures de données et complexité

Une 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.

Une 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.

Un 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.

La 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.