Complexité d'un nombre entier

Un article de Wikipédia, l'encyclopédie libre.

La complexité d'un nombre entier est le nombre minimal de 1 nécessaires pour écrire ce nombre en n'utilisant que :

Quelques exemples[modifier | modifier le code]

  • Il est évident que 1+1=2 est l'écriture la plus simple, donc la complexité de 2 est 2.
  • 4 = 1+1+1+1, mais aussi 4=(1+1)×(1+1). Cependant, aucune écriture de 4 n'est possible avec moins de quatre 1.
  • 6 = 3×2 = (1+1+1)×(1+1) donc la complexité de 6 est 3+2=5.

Propriétés[modifier | modifier le code]

On déduit assez simplement de la définition un premier résultat, en notant C(n) la complexité d'un entier n.

Propriété — Si a, b et c sont des entiers naturels tels que a = b×c, alors C(a)≤C(b)+C(c)

Cette propriété peut être combinée avec la décomposition en produit de facteurs premiers : la complexité d'un nombre est inférieure ou égale à la somme des complexités de ses facteurs premiers. Par exemple, 9 = 32 donc C(9) ≤ C(3)+C(3), donc C(9)≤6. Seule une analyse plus poussée permet de conclure que C(9) = 6.

Cependant, ce dernier résultat n'est pas optimal : la complexité de 23 est 11, celle de 2 est 2. Or 46 = (1+1+1)×(1+1+1)×((1+1)×(1+1)+1)+1 : la complexité de 46 est 12.

Un algorithme[modifier | modifier le code]

En utilisant les propriétés ci-dessus et la remarque que chaque nombre premier est égal au nombre précédent+1, on peut s'approcher de la complexité en suivant l'algorithme récursif ci-dessous :

  • si n est premier, on applique l'algorithme à n-1 (la complexité de n étant inférieure ou égale à celle de n, moins 1);
  • si n n'est pas premier, on l'applique à chacun de ses facteurs premiers.

Jusqu'à obtenir des nombres dont on connaît la complexité. Ensuite, on additionne les résultats trouvés.

Cet algorithme donne un majorant de la complexité. Appliqué à 235, il donne 19 alors que la complexité de 235 est 17.

Algorithme parfait ?[modifier | modifier le code]

Il est bien sûr possible, en théorie, de trouver un algorithme pour calculer la complexité d'un nombre n : il suffit de tester toutes les combinaisons possibles de n (ou moins) signes 1 avec + , × et parenthèses. Mais la complexité (de l'algorithme, cette fois) est exponentielle. On peut réduire la complexité de l'algorithme en décomposant n en facteurs premiers, mais cela revient à résoudre le problème de la décomposition en produit de facteurs premiers d'un nombre, qui est tout aussi complexe. Et cela ne résout pas le problème du calcul de la complexité d'un nombre premier.

Bibliographie[modifier | modifier le code]

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Complexité_d%27un_nombre_entier&oldid=91322994 ».