Réseau Graphes P. Fonctionnelle P. Logique Complexité

L3

Trucs à savoir

Théorème de la méthode générale / master theorem

Pour résoudre les récurrence du genre T(n) = a · T(n/b) + f(n) avec a ≥ 1 et b > 1.

• Cas 1: n^log_b(a) > f(n)
• Cas 2: n^log_b(a) = f(n)
• Cas 3: n^log_b(a) < f(n)

Une fois le cas trouvé, on détermine la complexité:

• Cas 1: T(n) = O(n^log_b(a)).
• Cas 2: T(n) = O(n^log_b(a) · log₂(n))
• Cas 3: T(n) = O(f(n)).

Propriétés du logarithmes

• log_n(m^p) = p · log_n(m)
• log_n(n) = 1

Documents

• Fiche de TD n°3
• Fiche de TD n°4
• Correction DS