Résultats pour « Complexité »
Complexité des algorithmes : Méthode de comptage des pas
La méthode de comptage des pas est une technique systématique pour analyser la complexité temporelle d'un algorithme : On identifie les instructions élémentaires et on compte leur nombre d'exécutions.
Complexité temporelle et spatiale
Lorsqu'on analyse un algorithme, on s'intéresse à deux ressources fondamentales : le temps et l'espace mémoire. Ces deux mesures permettent d'évaluer l'efficacité d'un algorithme et de comparer différentes solutions pour un même problème.
Algorithmes de tri élémentaires (Tri sélection, tri par insertion et tri à bulles)
Problème du tri Étant donné un tableau T[0..n-1] de n éléments comparables, trier consiste à réorganiser les éléments de façon à obtenir T[0] ≤ T[1] ≤ … ≤ T[n-1]. Les trois algorithmes présentés ici sont dits élémentaires : simples à comprendre et à implémenter, mais de complexité O(n^2) dans le pire cas — à utiliser sur de petits tableaux ou comme base pédagogique.
Recherche dichotomique et méthodes associées en C++ - Bibliothèque STL
Les méthodes de recherche dichotomique supposent que la séquence est déjà triée et offrent des performances de complexité supérieures à celles de la recherche classique sur une séquence non triée.
Analyse des algorithmes - Opérations élémentaires et modèles de coût
Nous voulons souvent raisonner sur le temps d'exécution d'une manière qui ne dépend que de l'algorithme et de son entrée. Ceci peut être réalisé en choisissant une opération élémentaire, que l'algorithme effectue à plusieurs reprises, et en définissant la complexité temporelle \(T(n)\) comme le nombre de ces opérations que l'algorithme effectue étant donné un jeu de données de longueur n.
Complexité temporelle : Méthode de comptage des pas pour les boucles
pour la boucle for le coût est proportionnel au nombre d'itérations, par contre pour une une boucle while, il faut estimer le nombre d'itérations.
convertir une boucle Pour imbriquée en une boucle Pour simple
Cette technique montre comment une boucle for imbriquée dans quelques problèmes peut être convertie en une seule boucle for, pour réduire la complexité du programme
Analyse d'algorithmes : Notations asymptotiques
Lorsqu'on analyse un algorithme, on cherche à connaître son comportement pour des entrées de grande taille. Au lieu de mesurer le temps exact d'exécution (qui dépend des machines), on utilise des notations asymptotiques qui permettent de donner une estimation générale de la croissance de la fonction de complexité.
Exercices corrigés Python (complexité)
Cette série d'exercices porte sur la récursivité et l'analyse de complexité des algorithmes. Vous serez amené à écrire des fonctions récursives pour résoudre divers problèmes et à estimer leur complexité temporelle.