Discussion :

[info_sara]

Bonjour,
je veux calculer la complexité d'un algorithme
fiure11 dans cette article
https://www.personalrobotics.ri.cmu....karbitrary.pdf

Pour moi, je vois qu elle est d'ordre O(n^3)
parce que il y as trois boucle, et j'ai mis les instruction ordre O(1) mais je sens que je me trompel parec que il y a le calcul de la matrice pseudo inverse , jacobien...

[dourouc05]

Calculer une jacobienne est très loin de se faire en temps constant (à moins de considérer une matrice de taille constante, ce qui n'a généralement pas de sens pour la complexité d'un algorithme), par exemple. En considérant un espace à n variables et une fonction à m valeurs, la matrice en sortie a une dimension ; évaluer une colonne nécessite une application de la formule des différences finies (ensuite, tu détailles le calcul des différences finies pour l'évaluation de la jacobienne, pour en déterminer le nombre d'opérations, donc la complexité).

Très clairement, compter les boucles est très insuffisant. D'ailleurs, que représente n dans ta notation ?

[info_sara]

Merci pour la réponse
n représente le nombre de jointure

alors comment je calcule dans ce cas la complexité de cette algorithme ?

[dourouc05]

Dans le cas de méthodes numériques itératives, cette notion de complexité est rarement utilisée : ici, il faudrait déterminer le nombre d'itérations à effectuer pour que les conditions "clamping detected" et "constraints met" soient remplies (pour la première boucle, c'est assez simple : elle est exécutée p fois, en utilisant les notations de l'article). Par contre, tu peux exprimer la complexité d'une itération (pas forcément de la boucle extérieure !) et une borne sur le nombre d'itérations à effectuer selon la précision souhaitée (par exemple, pour le gradient conjugué, , avec le nombre de conditionnement de la matrice du système et la précision souhaitée).

[info_sara]

En faite je n'ai pas ben compris ce que vous voulez me dire exactement