Scribd
Importer
33 vues2 pages

Cours Complexité

Ce document présente une introduction à l'algorithmique, incluant une définition et un exemple d'algorithme pour déterminer la présence d'un élément dans un tableau. Il décrit les caractéristiques d'un algorithme, telles que la déclaration des variables et l'écriture en langage naturel, ainsi que la notion de complexité, qui évalue l'efficacité d'un algorithme en termes de temps et d'opérations élémentaires. La complexité est analysée dans le pire des cas, avec un focus sur l'ordre de grandeur asymptotique O(n).

Transféré par

iyadsfia2008
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
33 vues2 pages

Cours Complexité

Ce document présente une introduction à l'algorithmique, incluant une définition et un exemple d'algorithme pour déterminer la présence d'un élément dans un tableau. Il décrit les caractéristiques d'un algorithme, telles que la déclaration des variables et l'écriture en langage naturel, ainsi que la notion de complexité, qui évalue l'efficacité d'un algorithme en termes de temps et d'opérations élémentaires. La complexité est analysée dans le pire des cas, avec un focus sur l'ordre de grandeur asymptotique O(n).

Transféré par

iyadsfia2008
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Introduction à l’algorithmique

Définition :

Exemple : écriture d’un algorithme


Trouver la suite d'opérations élémentaires qui permettra de répondre à la question : "x est-il
présent dans le tableau t ?".

VARIABLE
t : tableau d’entiers
x : nombre entier
tr : booléen (VRAI ou FAUX)
i : nombre entier
DEBUT
tr ← FAUX
i←1
tant que i ≤ longueur(t) et que tr == FAUX :
si t[i] == x :
tr ← VRAI
fin si
i ← i+1
fin de tant que
renvoyer la valeur de tr
FIN

Caractéristiques :
• on définit les variables que l'on va utiliser en précisant leur type (= déclaration des
variables) ;
• on doit indiquer le début et la fin de l'algorithme ;
• écriture en langage naturel ;
• implémenter un algorithme = passage à un langage de programmation ;
• le premier élément d'un tableau a pour indice 1 ;
• on s’autorise à écrire qu’une fonction est considérée comme une opération « élémentaire »
(ex : longueur(t)) ;
• un algorithme s’exécute avec du papier et un crayon (= on le fait tourner « à la main »).
Complexité :
• elle rend compte de l’efficacité de l’algorithme ;
• en temps = liée au nombre d'opérations élémentaires qui doivent être exécutées afin de
résoudre le problème donné ;
• en mémoire (pas abordé) ;
• dans la suite, on s’intéressera à la complexité en temps dans le pire des cas, c’est-à-dire,
lorsqu’il y a le plus grand nombre d’opérations élémentaires ;
• pour comparer des algorithmes, on raisonnera sur des tableaux de grande taille (cela rend
flagrantes les différences) ;
• O = ordre de grandeur asymptotique (cas où n est très très grand) ; on écrit O(n) = …. ;
• dans le cas où on obtient, comme nombre d’opérations élémentaires, un polynôme de degrés
quelconque, il suffit de :
◦ supprimer la constante ;
◦ garder uniquement le n qui possède l'exposant le plus grand ;
◦ supprimer le coefficient devant le n ;
ex : dans notre algorithme, O(n) = n.
En effet, on a enlevé 4. Puis, on a pris 1 comme exposant de n. Et on a supprimé 3.

Vous aimerez peut-être aussi