Discussion :

[xs4all]

Je m'embrouille vraiment avec la complexité, j'ai lu des trucs et j'ai vu en cours que disons un algorithme qui boucle sur l'entier n disons devrait avoir une complexité dans O(n), mais si on donne la complexité en fonction de la longueur du mot, cela devrait nous donner par la relation suivante (C'est un autre détail dont je ne suis pas sur...) n = 2^k-1 donc ce qui était linéaire devient exponentiel sur la longueur du mot. Est-ce qu'on doit utiliser la complexité sur n ou k?

Un autre truc qui me pause quelques problèmes, dans quel circonstance peut-on considérer l'addition, la soustraction, division, modulo, les operations booléenne <, >, == comme étant élémentaire ou tout encore est-ce qu'on peut les considérer comme élémentaire? J'ai lu que pour les entiers qui tienne sur 32bits(ou 64bits, bref dépendant de l'architecture de la machine) les opérations peuvent être considéré comme élémentaire, mais pour des entiers plus grands on ne pouvait pas, car la complexité de l'addition dépenderait de la longueur du nombre à additionner. Ce que je trouvais un peu spécial étant donner que la complexité était un moyen de ne pas se fier au limite d'une machine en particulier. Donc est-ce seulement en pratique qu'on fera attention au limite matériel ou bien même les algorithmes comme la multiplication classic en O(n^2), Karatsuba et Schönhage et Strassen tiennent compte du fait que leur addition ne sont pas élémentaires (dans le cas où il y aurais des additions non-élémentaire) lors du calcul de leur complexité?

Ça fait beaucoup de questions, mais je cherche des réponses depuis le début de la semaine, j'espère que l'info n'était pas déjà sur le forum, j'ai cherché, mais il y a tellement de post sur la complexité! Et si je n'ai pas été clair sur quelque chose, faites-moi en part et j'allumerai la lumière héhé!

[millie]

Je m'embrouille vraiment avec la complexité, j'ai lu des trucs et j'ai vu en cours que disons un algorithme qui boucle sur l'entier n disons devrait avoir une complexité dans O(n), mais si on donne la complexité en fonction de la longueur du mot, cela devrait nous donner par la relation suivante (C'est un autre détail dont je ne suis pas sur...) n = 2^k-1 donc ce qui était linéaire devient exponentiel sur la longueur du mot. Est-ce qu'on doit utiliser la complexité sur n ou k?

Effectivement, la complexité est théoriquement donné par rapport à la longueur du mot d'entrée (donc |n| = log(n)) d'où une complexité exponentielle par rapport à la longueur de n mais en O(n) (ici n correspond au n d'entrée, et pas à une variable)
Si n est le mot d'entrée et que la complexité est en O(n), la complexité est donc linéaire par rapport à n, mais exponentielle tout court quand on fait uniquement référence à des classes de complexité (genre P pour la classe des algorithmes de complexité polynomial par rapport à la taille des instances d'entrées)

Il y a parfois un abus de langage, ce qui n'aide pas.

Un autre truc qui me pause quelques problèmes, dans quel circonstance peut-on considérer l'addition, la soustraction, division, modulo, les operations booléenne <, >, == comme étant élémentaire ou tout encore est-ce qu'on peut les considérer comme élémentaire? J'ai lu que pour les entiers qui tienne sur 32bits(ou 64bits, bref dépendant de l'architecture de la machine) les opérations peuvent être considéré comme élémentaire, mais pour des entiers plus grands on ne pouvait pas, car la complexité de l'addition dépenderait de la longueur du nombre à additionner.?

Tu as bien entendu.

Ce que je trouvais un peu spécial étant donner que la complexité était un moyen de ne pas se fier au limite d'une machine en particulier.

En pratique, c'est rare qu'on travaille avec des entiers de taille non limité (donc pas sur 32 bits par exemple) donc on considère les opérations constantes (dès que l'on utilise "int" en C ou un type limité dans un autre langage, alors on peut considérer les opérations comme constantes)

Dès qu'il est nécessaire de travailler avec des entiers non limité (genre logiciel de calcul formel), alors il est obligatoire de prendre en compte la longueur.

[xs4all]

Bon la c'est plus clair Merci! Je croyais avoir découvert un algorithme pour multiplier des nombres en O(n), mais si j'ajoute les additions je suis dans O(n^2) ce qui ne vaut rien du tout... J'étais sur de faire un erreur quelque part et j'ai trouvé