Taille d'une donnée numérique — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 10)

Taille d'une donnée numérique

Complexité des programmes · niveau 3 (difficile)

Énoncé

Pour savoir si un entier $N \geq 2$ est premier, on essaie de le diviser par tous les entiers $d$ tels que $2 \leq d$ et $d^{2} \leq N$ .

Quel est le nombre de divisions dans le pire cas ? Le programme est-il « en $Θ (N)$ » ?
La taille de la donnée est le nombre $c$ de chiffres de $N$ . Exprimer la complexité en fonction de $c$ . Ce programme est-il polynomial ?
Estimer le temps de calcul, à $1 0^{9}$ divisions par seconde, pour un nombre premier de $18$ chiffres, puis de $30$ chiffres. Faire le rapprochement avec la complexité pseudo-polynomiale du sac.

Le pire cas est celui d'un nombre premier : aucune division ne réussit et l'on essaie $⌊ N ⌋ - 1$ diviseurs. Le nombre de divisions est bien en $Θ (N)$ , mais $N$ n'est pas la taille de la donnée.
Un nombre de $c$ chiffres vérifie $1 0^{c - 1} \leq N < 1 0^{c}$ , donc $N$ est de l'ordre de $1 0^{c /2} = (10)^{c}$ : la complexité est exponentielle en la taille $c$ . Le programme n'est pas polynomial.
Pour $c = 18$ : environ $1 0^{9}$ divisions, une seconde. Pour $c = 30$ : environ $1 0^{15}$ divisions, plus de $11$ jours. Douze chiffres de plus multiplient le temps par un million. Le sac de valeur maximum est dans la même situation : $Θ (n C)$ est polynomial en la valeur de $C$ , mais exponentiel en son nombre de chiffres (complexité pseudo-polynomiale).