Complexite d'un algorithme
Fermé
farfatou_8
-
9 mars 2009 à 18:19
mamiemando Messages postés 32302 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 28 mars 2023 - 10 mars 2009 à 00:49
mamiemando Messages postés 32302 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 28 mars 2023 - 10 mars 2009 à 00:49
A voir également:
- Complexite d'un algorithme
- Ppcm algorithme - Forum Programmation
- Ecrire un algorithme qui permet de resoudre ax²+bx+c=0 - Forum Algorithmes / Méthodes
- Pgcd algorithme - Forum Programmation
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Algorithme excel - Forum VB / VBA
1 réponse
mamiemando
Messages postés
32302
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
28 mars 2023
7 576
10 mars 2009 à 00:49
10 mars 2009 à 00:49
En fait pour parler de complexité il faut d'abord se demander "par rapport à quoi". N'importe quel traitement informatique a en soit une complexité. Par exemple en soit, une addition sera en O(n) ou n est le nombre de digit permettant de décrire un nombre. Une division sera bien entendu plus coûteuse.
Maintenant ce qu'il faut voir c'est que ce nombre de digit est borné (par exemple 32 bits pour un entier sur une architecture 32 bits) donc en général on les associe à un temps constant (O(1)). C'est surtout un niveau de détail qui est invisible pour toi, donc quand tu évalues la complexité d'un algorithme tu ne le prends pas en compte, d'autant plus que l'implémentation d'une opération de bas niveau peu changer d'une plate-forme à l'autre.
Conclusion : dans ton cas il faut uniquement t'intéresser à la complexité induite par des boucles ou des appels récursifs. Ils sont de toutes manières beaucoup plus sensibles en terme de performance. Par exemple en recherche opérationnelle, une méthode de résolution dont la complexité est polynomiale devient nettement plus rapide qu'une méthode de résolution dont la complexité est exponentielle dès que l'instance à résoudre grossit un peu.
Ainsi, si on te donne une matrice positive M de taille m x n et que tu doives calculer la racine carré de chaque terme Mij, le programme ressemblera à :
Soit une complexité O(n.m) (algorithme polynomial).
Si cependant tu t'intéresses à la manière dont est calculé une racine carrée ou une fonction mathématique de base, le mieux serait de te référer à des ouvrages de programmation de librairie mathématiques.
Bonne chance
Maintenant ce qu'il faut voir c'est que ce nombre de digit est borné (par exemple 32 bits pour un entier sur une architecture 32 bits) donc en général on les associe à un temps constant (O(1)). C'est surtout un niveau de détail qui est invisible pour toi, donc quand tu évalues la complexité d'un algorithme tu ne le prends pas en compte, d'autant plus que l'implémentation d'une opération de bas niveau peu changer d'une plate-forme à l'autre.
Conclusion : dans ton cas il faut uniquement t'intéresser à la complexité induite par des boucles ou des appels récursifs. Ils sont de toutes manières beaucoup plus sensibles en terme de performance. Par exemple en recherche opérationnelle, une méthode de résolution dont la complexité est polynomiale devient nettement plus rapide qu'une méthode de résolution dont la complexité est exponentielle dès que l'instance à résoudre grossit un peu.
Ainsi, si on te donne une matrice positive M de taille m x n et que tu doives calculer la racine carré de chaque terme Mij, le programme ressemblera à :
Pour i = 1 à m // O(n.m)
Pour j = 1 à n // O(n)
Mij = racine(Mij) // O(1)
Fin pour
Fin pour
Soit une complexité O(n.m) (algorithme polynomial).
Si cependant tu t'intéresses à la manière dont est calculé une racine carrée ou une fonction mathématique de base, le mieux serait de te référer à des ouvrages de programmation de librairie mathématiques.
Bonne chance