 |
|
|
| |
| TUTORIEL ALGO/METHODES |
|
|
|
| Complexité d'un algorithme |
| Présentation de la notation "grand O", permettant de noter la complexité d'un algorithme et la comparer à celle des autres.
(08/09/2005) |
  |
Qu'un algorithme
parvienne au bon résultat est une chose, encore faut-il qu'il
le fasse dans un temps raisonnable. Un algorithme peut ainsi
demander beaucoup de ressources (mémoires, temps, espace disque...)
pour parvenir à un résultat, tandis qu'un autre mieux conçu
le ferait de manière plus efficace.
Il faut dès lors choisir l'algorithme le plus approprié face
à une situation : un code pour une calculatrice à énergie solaire
disposera certainement de moins de ressources qu'un autre pour
vérifier le bon déroulement du décollage de la fusée Ariane.
Il s'agit donc d'évaluer les besoins en ressources d'un ou plusieurs
algorithmes, afin de les rattacher à une courbe connue ou à
les comparer entre eux. Étant donnés les prix en chute de la
mémoire et de l'espace disque, la complexité la plus pertinente
reste celle en temps. Par ailleurs, il est fréquent de devoir
sacrifier l'efficacité en stockage pour privilégier le temps
d'exécution.
On recense trois types de complexité :
- Complexité "dans le pire des cas" : situations où les
données obligent l'algorithme à un maximum d'itérations
- Complexite "dans le meilleur des cas" : situation où
les données autorisent l'algorithme à les traiter en un minimum
d'itérations
- Complexité moyenne : moyenne de toutes les situations
possibles
Chaque
cas d'utilisation devra être étudié selon les données à traiter.
Si l'on entre dans un cadre plus général, c'est la complexité
moyenne qui sera à prendre en compte. L'objectif est bien évidemment
que ce calcul de complexité se fasse indépendamment du processeur,
du type de mémoire, etc.
La comparaison de l'efficacité des algorithmes se fait grâce
à la notation "grand O" ("O" signifiant "de l'ordre de") ou
notation de Landon, qui décrit le comportement asymptotique
des fonctions mathématiques, et par extension permet d'indiquer
la rapidité avec laquelle elle (ou sa courbe descriptive) augmente
ou diminue. Il existe également une notation "petit o".
En effet, les algorithmes ne peuvent décemment être testés sur
10 ou 100 possibilités, mais parfois dans des quantités astronomiques
(si l'algorithme est crucial). Les algorithmes connus sont donc
tous rattachés à l'une des notations grand O, qui permet de
savoir de quelle manière évolue une courbe temps/possibilités.
Cela permet de repérer d'un seul coup d'oeil les algorithmes
efficaces pour un très petit échantillon, ceux qui prennent
constamment le même temps...
Cette évolution des courbes peut suivre divers cadres connus
:
- x = y, quand l'augmentation est constante et quasiment
rectiligne
- x = log(y), quand elle correspond à celle du logarithme.
Ainsi, on dénombre un certain nombre de types de notations grand
O :
- O(1) : le traitement prend toujours le même temps, quel
que soit le nombre de données.
- O(n) : le temps de traitement est constamment proportionnel
au nombre de données, quasiment linéaire.
- O(n!) : le temps de traitement correspond à une factorielle
du nombre de données.
- O(log(n)) : évolution logarithmique
- O(n*log(n)) : évolution linéarithmique
- O(c^n) : évolution exponentielle
 |
Forum |
|
|
Réagissez
dans les forums
de JDN Développeurs
|
Ainsi, en rapprochant son algorithme d'une des notations grand
O, on est mesure de comparer directement son amplitude avec
celle d'un autre algorithme, et donc de voir lequel est le plus
approprié pour le travail à accomplir, ou le cadre dans lequel
il se réalise. |
|
|
|
|
|
|
|
| Quand achetez-vous le plus en ligne ? |
|
|
|
|
|
|
|
|
| |
|
