Complexite d'un algorithme
Bonjour,
Je souhaite calculer la complexite numerique d'un algorithme (sous forme d'equations) que j'ai developpe sur matlab.
J'ai surfe un peu sur internet et generalement, on considere seulement le cas d'algorithmes simples et aussi que des entiers. SVP, comment fait on pour determiner la complexite d'une equation mathematique definie dans le domaine reel R ou complexe C. Autrement dit est ce que la division peut etre consideree comme operation elementaire comme la somme et la multiplication dans le cas des entiers? Comment determiner la complexite de la racine carre?
Voici un exemple d'equation:
[y-x*sqrt(y^2-x^2)]/(y-x)
Merci infiniment :)
Je souhaite calculer la complexite numerique d'un algorithme (sous forme d'equations) que j'ai developpe sur matlab.
J'ai surfe un peu sur internet et generalement, on considere seulement le cas d'algorithmes simples et aussi que des entiers. SVP, comment fait on pour determiner la complexite d'une equation mathematique definie dans le domaine reel R ou complexe C. Autrement dit est ce que la division peut etre consideree comme operation elementaire comme la somme et la multiplication dans le cas des entiers? Comment determiner la complexite de la racine carre?
Voici un exemple d'equation:
[y-x*sqrt(y^2-x^2)]/(y-x)
Merci infiniment :)
A voir également:
- Complexite d'un algorithme
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Algorithme euromillion excel gratuit - Forum Algorithmes / Méthodes
- Algorithme ajout rapide snapchat - Forum Snapchat
- Ajout rapide snap - Forum Snapchat
1 réponse
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
