Complexité des deux sacs

Complexité des programmes · niveau 2

Énoncé

On reprend le problème des deux sacs (chapitre 3) avec $n$ objets et des contenances $C_{0}$ et $C_{1}$ .

Quelle est la taille du tableau $M$ ? Quel est le temps de calcul d'une case ? En déduire la complexité en temps.
Si l'on ne veut que la valeur maximum, et non le contenu des sacs, combien de tranches $M [k]$ faut-il garder en mémoire à un instant donné ? En déduire la complexité en espace.

$M$ a $(n + 1) (C_{0} + 1) (C_{1} + 1)$ cases. Chacune se calcule en temps constant (le maximum d'au plus trois valeurs, déjà calculées). La complexité en temps est $Θ (n C_{0} C_{1})$ , et c'est aussi la complexité en espace du programme du cours.
L'hérédité n'utilise que la tranche $M [k - 1]$ pour calculer $M [k]$ . Deux tranches de $(C_{0} + 1) (C_{1} + 1)$ cases suffisent : la complexité en espace tombe à $Θ (C_{0} C_{1})$ , la complexité en temps est inchangée. Mais on perd la reconstruction des sacs, qui a besoin de toutes les tranches.

100 % gratuit

La suite du chapitre est sur Adloun

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