Quelle option préférerez-vous?

Faire des allers-retours à vélo plusieurs fois à l’épicerie avec un seul sac ou une seule fois mais en traînant une grande remorque à vélo
Trouver votre chemin vers la maison d’un nouvel ami en prenant des virages au hasard aux intersections de la route jusqu’à ce que vous arriviez (peut-être des années plus tard) ou en prenant le virage qui vous mène dans la direction générale et en revenant sur vos pas si nécessaire jusqu’à ce que vous arriviez

Définitions

Analyse algorithmique: Décrire la complexité des algorithmes - combien de temps ou combien d’espace ils prennent pour accomplir la tâche. Certains algorithmes sont beaucoup plus efficaces avec les opérations ou la mémoire que d’autres. Certains sont tellement inefficaces qu’ils ne sont pas du tout pratiques!
Ordre de grandeur: Nombre d’étapes ou de la quantité de mémoire requise en fonction de la taille des données à traiter, décrit selon le terme le plus important dans la relation. L’ordre de grandeur n’est donc pas une relation exacte entre l’effort et le nombre de données à traiter mais donne un portrait de la progression globale de l’effort selon ce nombre.
Notation “grand O”: Représentation de l’ordre de grandeur au format O(f(n)) où f(n) est une fonction qui décrit la complexité de l’algorithme en fonction de la taille des données à traiter. Par exemple, O(n) signifie que l’effort est proportionnel à la taille des données, n, tandis que O(n²) signifie que l’effort est proportionnel au carré de la taille des données.

Objectifs d’apprentissage

À la fin de cette leçon vous devrez être en mesure de :

Définir la complexité algorithmique, l’efficacité temporelle, l’efficacité spatiale et les problèmes P/NP
Définir les niveaux de complexité algorithmique courants dans la notation “grand O” : constant, logarithmique, linéaire, log-linéaire, quadratique et exponentiel
Identifier les strutures algorithmiques qui conduisent à une complexité constante, linéaire, logarithmique, quadratique ou exponentielle

Critères de succès

Je peux reconnaître la complexité “grand O” d’un algorithme en fonction de son graphique d’opérations (ou d’utilisation de la mémoire) en fonction de la taille de l’entrée
Je peux identifier la complexité de la recherche séquentielle et binaire ainsi que celle de quelques algorithmes de tri courants
Je peux analyser un algorithme inconnu pour déterminer sa complexité algorithmique en fonction des structures observées dans l’algorithme