Tri fusion : implémentation et preuve

Difficile

Écrire la fonction fusion(L1, L2) qui fusionne deux listes triées en une liste triée. Prouver que sa complexité est

O(|L_1| + |L_2|)

Écrire la fonction tri_fusion(L) qui trie une liste par la méthode diviser pour régner.

Montrer par récurrence que la complexité vérifie

C(n) = O(n \log n)

Le tri fusion est-il stable ? Justifier.

La solution est réservée aux abonnés

L'énoncé est en libre accès. Les indices progressifs et la solution détaillée sont réservés aux abonnés Premium.

Tri fusion : implémentation et preuve

Difficile

Écrire la fonction fusion(L1, L2) qui fusionne deux listes triées en une liste triée. Prouver que sa complexité est

O(|L_1| + |L_2|)

Écrire la fonction tri_fusion(L) qui trie une liste par la méthode diviser pour régner.

Montrer par récurrence que la complexité vérifie

C(n) = O(n \log n)

Le tri fusion est-il stable ? Justifier.

L'énoncé est en libre accès. Les indices progressifs et la solution détaillée sont réservés aux abonnés Premium.