Scribd
Importer
1 vues2 pages

Algorithmes Guide

Ce guide pratique présente les concepts fondamentaux des algorithmes et de leur complexité, en mettant l'accent sur la notation Big O pour évaluer le temps d'exécution et la mémoire. Il décrit divers algorithmes de tri et leur performance, ainsi que des exemples de recherche, notamment la recherche binaire. Enfin, il aborde les structures de données et leur complexité, soulignant l'importance de choisir la bonne structure pour optimiser les performances.

Transféré par

dylanelokossousoton
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
1 vues2 pages

Algorithmes Guide

Ce guide pratique présente les concepts fondamentaux des algorithmes et de leur complexité, en mettant l'accent sur la notation Big O pour évaluer le temps d'exécution et la mémoire. Il décrit divers algorithmes de tri et leur performance, ainsi que des exemples de recherche, notamment la recherche binaire. Enfin, il aborde les structures de données et leur complexité, soulignant l'importance de choisir la bonne structure pour optimiser les performances.

Transféré par

dylanelokossousoton
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

ALGORITHMES · GUIDE PRATIQUE 1/2

Algorithmes & Complexité


Tris, recherche et notation Big O — les bases du raisonnement algorithmique

Qu'est-ce que la complexité algorithmique ?


La notation Big O mesure comment le temps d'exécution ou la mémoire d'un algorithme évolue en fonction de la
taille des données (n). C'est l'outil standard pour comparer des algorithmes indépendamment du matériel.

Notation Nom Exemple n=1000

O(1) Constant Accès tableau par index 1 op

O(log n) Logarithmique Recherche binaire ~10 op

O(n) Linéaire Parcours de liste 1 000 op

O(n log n) Quasi-linéaire Merge Sort ~10 000 op

O(n²) Quadratique Bubble Sort 1 000 000 op

O(2■) Exponentiel Sous-ensembles Inutilisable

Algorithmes de tri à connaître

Algorithme Meilleur Moyen Pire Stable

Bubble Sort O(n) O(n²) O(n²) Oui

Selection Sort O(n²) O(n²) O(n²) Non

Insertion Sort O(n) O(n²) O(n²) Oui

Merge Sort O(n log n) O(n log n) O(n log n) Oui

Quick Sort O(n log n) O(n log n) O(n²) Non

Document éducatif · ALGORITHMES · GUIDE PRATIQUE © 2025


ALGORITHMES · GUIDE PRATIQUE 2/2

Recherche binaire — exemple


La recherche binaire divise le problème en deux à chaque étape — O(log n) au lieu de O(n) pour une recherche
linéaire. Nécessite un tableau trié.

def recherche_binaire(tableau, cible):

gauche, droite = 0, len(tableau) - 1

while gauche <= droite:

milieu = (gauche + droite) // 2

if tableau[milieu] == cible:

return milieu # trouvé

elif tableau[milieu] < cible:

gauche = milieu + 1 # chercher à droite

else:

droite = milieu - 1 # chercher à gauche

return -1 # non trouvé

Structures de données et leur complexité

Structure Accès Recherche Insertion Suppression

Tableau O(1) O(n) O(n) O(n)

Liste chaînée O(n) O(n) O(1) O(1)

Hash Table O(1) O(1) O(1) O(1)

BST (équilibré) O(log n) O(log n) O(log n) O(log n)

Pile / File O(n) O(n) O(1) O(1)

À retenir : choisir la bonne structure de données résout souvent le problème de performance avant
même d'optimiser l'algorithme. Hash Table = O(1) pour tout — c'est la structure la plus puissante du
quotidien.

Document éducatif · ALGORITHMES · GUIDE PRATIQUE © 2025

Vous aimerez peut-être aussi