Discussion :

[AI_user02000]

Bonjour,
Quelqu'un pourrait-il m'aider à trouver la complexité de cet algorithme:
Pour i de 1 à n
i=2^i

Merci

[WhiteCrow]

Bonjour,
tu as essayé de te faire une idée des valeurs successives ?
tu sais que ce n'est jamais une bonne idée de modifier le variable index d'une boucle dans la boucle …
connais-tu la notation des exposants itérés de Knuth ? sais-tu ce que représente dans cette notation 2↑↑n ?

[AI_user02000]

Bonjour,
tu as essayé de te faire une idée des valeurs successives ?
tu sais que ce n'est jamais une bonne idée de modifier le variable index d'une boucle dans la boucle …
connais-tu la notation des exposants itérés de Knuth ? sais-tu ce que représente dans cette notation 2↑↑n ?

bONJOUR,
Effectivement j'ai pu voir comment varier les valeurs de i à chaque itération mais je n'arrive pas à trouver une expression générale. Et non malheureusement c'est la première fois que j'en entends parlé

[WhiteCrow]

Et avec la puissance itérée ?
Donc j'imagine que tu n'en connais pas l'inverse : le logarithme itéré (aka log*) ?

Avec tout ce que tu viens de découvrir, arrives-tu à une solution ?

[wiwaxia]

Bonjour,

Bonjour,
Quelqu'un pourrait-il m'aider à trouver la complexité de cet algorithme:
Pour i de 1 à n
i=2^i

Ne s'agirait-il pas plutôt de la relation u_i+1 = 2^u_i ?

Cela redeviendrait compréhensible.

[AI_user02000]

Peut on alors dire que la complexité est logarithmique?

[WhiteCrow]

Non, elle largement sous logarithmique. La complexité temporelle est à vue de nez en O( log* n ) ou similaire. C'est une fonction qui croît hyper lentement bien plus lentement qu'un log puisque c'est la fonction inverse d'une puissance itérée qui croît bien plus rapidement qu'une exponentielle. Par exemple pour le code que tu donnes, il n'y aura pratiquement jamais plus de 3 tours de boucle … ici pratiquement signifie «en pratique avec les plateformes actuelles».

[Guesset]

Bonjour WhiteCrow,

Non, elle largement sous logarithmique. La complexité temporelle est à vue de nez en O( log* n ) ou similaire. C'est une fonction qui croît hyper lentement bien plus lentement qu'un log puisque c'est la fonction inverse d'une puissance itérée qui croît bien plus rapidement qu'une exponentielle. Par exemple pour le code que tu donnes, il n'y aura pratiquement jamais plus de 3 tours de boucle … ici pratiquement signifie «en pratique avec les plateformes actuelles».

Oui, mathématiquement par rapport à n.

Mais un algorithme travaille dans le concret qui n'a pas l'élégance des mathématiques :

• Comme tu l'as fait remarquer, c'est une très mauvaise idée de modifier l'indice d'une boucle dans la boucle. Premier effet, si n est supérieur à 1 et n'est pas une puissance de 2 (et pas n'importe quelle puissance, voir juste après) aucun espoir d'un arrêt quelconque (sauf si le langage transforme implicitement l'égalité i = n en i >= n)
• La taille est très rapidement un autre problème ingérable même avec des grands nombres et des exposants, car les exposants devraient également être des grands nombres avec des exposants qui... (ce sont également les valeurs de n "acceptables") i₀ = 1, i₁ = 2, i₃ = 4, i₄ = 2¹⁶, i₅ =2⁶⁵⁵³⁶...
• Le problème devient plus intéressant si on suppose que le langage utilisé fait un modulo 2^a sans manifester une mauvaise volonté hautement probable (a caractérisant la longueur du type d'entier non signé utilisé), la boucle reste infinie... mais à 0.

En résumé, ou il fait très peu de pas et tend alors vers une complexité en O(0) mais pour peu de valeurs, ou il tourne sans fin O(oo)

Je ne suis pas sûr que ce soit vraiment intéressant. En revanche, je n'ai aucun doute sur l'utilité

Salut