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é!
