algorithmique (école d'ingénieur) · Chapitre 10 · Exercice de TD

Quand la taille double

Complexité des programmes · niveau 1 (application)

Énoncé

Un programme résout un problème de taille $n = 1000$ en une seconde.

Combien de temps lui faut-il pour $n = 2000$ si sa complexité est $Θ (n)$ , $Θ (n lo g n)$ , $Θ (n^{2})$ , $Θ (n^{3})$ , $Θ (2^{n})$ ? (On suppose le temps exactement proportionnel au terme dominant.)
Quelle taille peut-il traiter en une minute, dans chacun de ces cas ?

Corrigé

On écrit $t (n) = α f (n)$ avec $t (1000) = 1$ s.

Complexité	$t (2000)$	taille traitée en $60$ s
$Θ (n)$	$2$ s	$60000$
$Θ (n lo g n)$	$\approx 2, 2$ s	$\approx 39000$
$Θ (n^{2})$	$4$ s	$100060 \approx 7700$
$Θ (n^{3})$	$8$ s	$1000360 \approx 3900$
$Θ (2^{n})$	$2^{1000}$ s	$1000 + lo g_{2} 60 \approx 1005$

Pour $n lo g n$ : $2 lo g 2000/ lo g 1000 \approx 2, 2$ . Pour $2^{n}$ : on multiplie le temps par $2^{1000}$ , nombre qui dépasse de très loin l'âge de l'Univers en secondes ; et soixante fois plus de temps ne permet de traiter que $6$ éléments de plus.

100 % gratuit

La suite du chapitre est sur Adloun

Exercice suivant et tuteur

Sans compte : le cours et le premier QCM. Exercices et tuteur : inscription gratuite en 30 secondes, sans carte bancaire.

Le cours du chapitre · Tous les exercices du chapitre

Exercice suivant et tuteur →