Le coût réel des grands entiers

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 11 — La représentation des nombres

Énoncé

Expliquer pourquoi la complexité temporelle d'une exponentiation rapide calculant $2^{n}$ en multi-précision n'est pas simplement en $O (lo g n)$ .

Corrigé

Bien que l'algorithme n'effectue que $O (lo g n)$ multiplications, la taille des entiers manipulés double à chaque étape. Les dernières multiplications portent sur des entiers géants ayant jusqu'à $n$ bits de stockage. La complexité d'une multiplication de taille $d$ n'est pas en $O (1)$ mais croît au moins de façon linéaire en $O (d)$ . La complexité totale de l'exponentiation est donc dominée par la dernière multiplication de taille $n$ , rendant le coût global linéaire ou supra-linéaire en fonction de la taille finale.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.