Complexité d’un algorithme : La complexité d’un algorithme mesure le nombre d’opérations élémentaires qu’il effectue en fonction de la taille de l’entrée, notée n. Elle permet d’évaluer l’efficacité de l’algorithme en termes de temps de traitement.
Notation de Landau (O) : La notation O, ou notation asymptotique, sert à classer les algorithmes selon leur comportement lorsque n tend vers l’infini. Elle indique la limite supérieure du nombre d’opérations en fonction de n, en ignorant les constantes et termes de moindre ordre.
Complexité constante O(1) : Un algorithme a une complexité constante si le nombre d’opérations ne dépend pas de n. Il effectue un nombre fixe d’opérations, quel que soit la taille de l’entrée.
Complexité linéaire O(n) : La complexité est linéaire lorsque le nombre d’opérations croît proportionnellement à n. L’algorithme doit parcourir ou traiter chaque élément de l’entrée une seule fois.
Complexité logarithmique O(ln(n)) : La complexité logarithmique indique que le nombre d’opérations croît en fonction du logarithme de n. Elle est typique des algorithmes qui divisent l’espace de recherche à chaque étape, comme la recherche dichotomique.
1. Quelle est la cause principale de la rapidité de convergence de la recherche dichotomique ?
2. Selon le texte, à quel moment la stratégie de sélection du plus tôt dans le planning d’occupation a été démontrée comme optimale ?
3. Quelle propriété du système monétaire garantit que l’algorithme glouton donne toujours la solution optimale pour le rendu de monnaie ?
Complexité algorithme — définition ?
Mesure du nombre d'opérations en fonction de n.
Notation O — rôle ?
Classe et compare la croissance asymptotique.
Complexité constante O(1) — description ?
Opérations fixes, indépendantes de n.
Complexité linéaire O(n) — description ?
Proportionnelle à la taille n.
Complexité logarithmique O(ln(n)) — description ?
Croît en fonction du log de n.
Complexité quadratique O(n²) — description ?
Proportionnelle au carré de n.
La fiche de révision couvre les notions essentielles de Maîtrise des algorithmes gloutons et dichotomie. Elle est structurée par thématiques pour faciliter l'apprentissage et la mémorisation, avec des définitions clés, des explications et des synthèses.
Lire la fiche complète →Le QCM contient 7 questions à choix multiples avec corrections détaillées et explications pour chaque réponse. Idéal pour tester vos connaissances et identifier vos lacunes.
Faire le QCM (7 questions) →Revizly propose 14 flashcards interactives sur Maîtrise des algorithmes gloutons et dichotomie. Chaque carte présente une question au recto et la réponse au verso, permettant une révision active et efficace basée sur la répétition espacée.
Voir toutes les 14 flashcards →Bases de données
Bases de données
Programmation
Programmation
Importe ton PDF ou colle ton cours, l'IA génère fiches, QCM et flashcards en 30 secondes.