Examen 1 - Algorithmique Flashcards
2 grands types d’algorithme de recherche
Recherche linéaire (glouton)
Recherche dichotomique (diviser pour régner)
Quelle condition doit-on respecter avant de procéder à une recherche
dichotomique ?
Trier tableau/liste
C’est un critère de performance très important !
le nombre de comparaisons effectuées
Algorithmes de tri lent
Tri par sélection
Tri par insertion
Tri à bulles
Etc.
Algorithmes de tri rapides
Tri fusion
Tri rapide
Etc
On utilise le mot « complexité » algorithmique pour désigner…
l’efficacité d’un algorithme et non le fait qu’il comporte une
implémentation complexe (ou compliquée)
Il existe 2 sortes des complexités algorithmiques :
1) De temps
2) D’espace
expliquer complexité de temps
Nombre d’opérations élémentaires effectuées par un
algorithme
expliquer complexité d’espace
Nombre d’espace physique (essentiellement de la mémoire)
occupé par l’algorithme
la complexité est relative à notre contexte Exemple : Sur une plateforme qui offre peu de mémoire, les
algorithmes seront plus complexes que s’ils roulent sur des
plateformes offrant de grande possibilités physiques.
Solution : Utiliser un algorithme moins gourmand en espace
mémoire mais plus complexe (plus long) en temps !
Opérations élémentaires à surveiller pour complexité temps :
Comparaison
Affectation
Opérations arithmétiques
Tri par sélection
Étapes de l’algorithme
Initialisation : La liste entière est considérée comme non triée. Recherche du minimum : Parcourir la partie non triée pour trouver l'élément le plus petit. Mémoriser l'indice de cet élément. Échange : Échanger le plus petit élément trouvé avec le premier élément de la partie non triée. Mise à jour : Agrandir la partie triée en incluant le nouvel élément échangé. Réduire la partie non triée en conséquence. Répétition : Répéter les étapes 2 à 4 jusqu'à ce que toute la liste soit triée. Avantages : Simple à comprendre et à implémenter Performant pour de petites listes Nombre d'échanges limité (au maximum n-1)
Inconvénients :
Inefficace pour de grandes collections de données Toujours en O(n²), même si la liste est déjà triée Non stable
On dénote la complexité d’un algorithme avec le symbole…
“O”
O(n 2 ) Complexité quadratique
O(n) Complexité linéaire
O(n*log(n)) Complexité linéarithmique
O(log(n)) Complexité logarithmique
Tri-Fusion
Le tri fusion fonctionne en trois étapes principales :
Diviser : Séparer la liste en deux moitiés à peu près égales. Régner : Trier récursivement chaque moitié. Combiner : Fusionner les deux moitiés triées en une seule liste triée.
Algorithme détaillé
Si la liste contient 0 ou 1 élément, elle est déjà triée. Sinon : Diviser la liste en deux sous-listes de tailles égales (ou presque). Appliquer récursivement le tri fusion sur chaque sous-liste. Fusionner les deux sous-listes triées pour obtenir la liste finale triée.
Étape de fusion
La fusion est l’étape clé qui donne son efficacité à l’algorithme :
Comparer les éléments en tête de chaque sous-liste. Sélectionner le plus petit et l'ajouter à la liste fusionnée. Répéter jusqu'à ce que tous les éléments soient traités. O(n log n)
Algorithmes de recherche
Recherche séquentielle / linéaire (glouton)
Parcourt les éléments un par un jusqu'à trouver celui recherché Complexité : O(n) dans le pire cas Simple à implémenter mais inefficace sur de grandes collections O(n) Complexité linéaire
Recherche dichotomique
S'applique sur des données triées Divise l'espace de recherche par 2 à chaque étape Complexité : O(log n) Très efficace sur de grandes collections triées O(log(n)) Complexité logarithmique