algorithmique (école d'ingénieur) · Chapitre 10 · Application directe du cours
Exhaustif contre dynamique
Complexité des programmes · niveau 1 (application)
Énoncé
On veut résoudre le sac de valeur maximum avec objets et une contenance , sur une machine qui fait opérations élémentaires par seconde. Estimer le temps de calcul :
- de l'énumération exhaustive des sous-ensembles, en comptant opérations par sous-ensemble (calcul de sa taille et de sa valeur) ;
- de la programmation dynamique du chapitre 2.
Corrigé
- Il y a sous-ensembles, soit environ . À opérations chacun : opérations, c'est-à-dire secondes, un peu plus de heures. Avec objets, il faudrait plus d'un an et demi.
- Le tableau a cases, chacune calculée en temps constant (quelques opérations) : de l'ordre de opérations, soit environ milliseconde.
Le rapport dépasse . Et il se creuse : ajouter un objet double le temps de l'énumération, mais n'ajoute qu'une ligne au tableau .
100 % gratuit
La suite du chapitre est sur Adloun
- 11 autres exercices corrigés dans ce chapitre
- Les 2 QCM du chapitre, le premier sans compte
- Le tuteur, qui guide pas à pas sans donner la réponse
Sans compte : le cours et le premier QCM. Exercices et tuteur : inscription gratuite en 30 secondes, sans carte bancaire.