courss.py

Created on December 16, 2024
1.03 KB
La méthode "" diviser pour régner
» consiste à :
• décomposer un problème en un 
ou plusieurs sous-problèmes 
similaires au problème initial
mais
de taille fortement inférieure
et distincts les uns des autres,
que l’on traitera de façon 
récursive
• construire, à partir des 
solutions des sous-problèmes,
la solution au problème initial
Des cas de base, pour lesquel
les on ne fera par d’appels 
récursifs, devront bien sûr 
être identifiés et traités 
directement.
Remarque : si on décompose 
en un temps d(n) un problème 
de taille n en a sous-problèmes
similaires de taille environ 
n/b
et que l’on peut construire, 
à partir de leurs solutions,
celle du problème initiale en
un temps f(n)
alors la complexité temporelle
C(n) du problème suit la 
relation de récurrence C(n)=d
(n)+a C(n/b)+f (n)
et la terminaison de
l’algorithme repose sur 
la présence de cas de base 
atteignable(s) par les 
divisions successives de 
n par b.
Théorème (admis) : Si C 
(n)=ak C ( n
a )+O (nk) alors C (n)=O 
(nk log2 (n ))