ce matin il manquait de toute évidence un slide pour analyser d'où provient l'ordre de complexité en O(nlog(n)) du tri-fusion.
lien:
https://moodlearchive.epfl.ch/2018-2019/mod/resource/view.php?id=997748
La méthode utilisée est de faire le bilan de l'ensemble des sous-problèmes de fusion traités à un même niveau de profondeur d'appel résursif.Quand on passe d'un niveau de profondeur au suivant, le doublement du nombre de sous-problèmes est compensé par la réduction de moitié de la taille de chaque sous-problème.
le bilan pour chaque niveau de profondeur est un coût linéaire O(n) qui provient du coût linéaire de la fusion.
ce coût (par niveau) est multiplié par le nombre de niveaux de profondeur: sachant qu'on divise la taille par 2 à chaque appel récursif, le nombre maximum d'appels récursifs est de l'ordre de O(Log2(n)).
Le coût total est donc O(n log(n)) .
rem: on peut se passer d'indiquer la base du log dans la notation de Landau en O(...) car elle est équivalente à un facteur scalaire.
