Intro Algorithmique Flashcards
Def : Analyse de complexité/efficacité des algorithmes
Déterminer les ressources utilisées pour exécuter l’algorithme.
Déf : Comment se mesure l’Efficacité des algorithmes
Se mesure par la quantité de ressources
utilisées.
● Le temps d’exécution
● L’espace mémoire utilisé
● La bande passante utilisée
Définition: le temps d’exécution d’un algorithme
est nombre d’opérations
élémentaires qu’il doit effectuer pour accomplir sa tâche.
Déf : Une opération élémentaire
est une opération non divisible.
Notation O
Détermine une borne supérieure éventuelle
Notation Ω
Détermine une borne inférieure éventuelle
Interprétation de
lim f(n)/g(n) n->∞
● = c > 0 alors f(n) en Θ(g(n))
● = 0 alors f(n) ∈ O(g(n)) et pas en Θ(g(n))
● = +∞ alors f(n) ∈ Ω(g(n)) et pas en Θ(g(n))
La règle de l’Hôpital
lim f(n)/g(n) n->∞
=
lim f’(n)/g’(n)
n->∞
Déf : Opération baromètre
opération élémentaire qui, À UNE CONSTANTE PRÈS, est effectuée au moins aussi souvent que n’importe quelle
autre opération élémentaire de l’algorithme.
Déf : Temps d’exécution en “Pire cas”
est le temps d’exécution
maximal parmi toutes les instances S de taille n.
Déf : Temps d’exécution en “Meilleur cas”
est le plus petit temps
d’exécution parmi toutes les instances S de taille n.
Déf :Le temps d’exécution moyen
est la moyenne des temps
d’exécution parmi toutes les instances S de taille n
Quand avons nous Tworst(n) = Tbest(n) = Tavg(n).
Lorsque le temps d’exécution ne dépends que de la taille n de l’instance
(et seulement dans ces cas)
Déf : Relation de récurrence
est une relation entre une fonction f
: N → R+ et elle même, évaluée sur une entrée plus petite.
Ex: f(n) = f(n-1) + 1.
Déf : Éventuellement non décroissante
Une fonction non négative f : N → R+ est dite
éventuellement non décroissante s’il existe n0 telle que f(n) ≤ f(n+1)
pour tout n ≥ n0.
Déf : Fonction harmonieuse sur R+
est dite harmonieuse lorsqu’elle est
éventuellement non décroissante et que f(2n) ∈ Θ(f(n)).
n³ est harmonieuse ?
Oui. car f(2n) = (2n)³ = 8n³ = 8f(n) ∈ Θ(f(n))
log(n) est harmonieuse ?
Oui. car log(2n) = log(2)+log(n) ∈ Θ(log n)
Théorème: Soit f(n) une fonction harmonieuse. Si T(n) est
éventuellement non décroissante et que T(n) ∈ Θ(f(n)) pour n = bk avec
b ≥ 2, alors …
alors T(n) ∈ Q(f(n)) (pour toutes les autres valeurs de n infiniment grandes).
Déf : Algorithme Récursif
● L’algorithme résout un (ou des) cas particulier(s) du problème d’une
façon simple et non récursive.
● Le cas général est solutionné par des appels récursifs successifs qui
doivent converger au(x) cas particulier(s).
● Il y a donc une condition d’arrêt qui permet de toujours
arrêter la cascade d’appels récursifs afin de
