Diviser pour Régner (DPR)

Introduction

Anglais : Divide and Conquer

Dans les situations où on souhaite résoudre un problème de taille , il peut être plus facile de diviser le problème en 2 avant de le résoudre : passer ainsi à deux problèmes . En informatique, on appelle cette méthode Diviser pour Régner (DPR). Il se décompose en 3 étapes :

1. Diviser le problème en plus petit problèmes (jusqu'à une taille de 1).
2. Résoudre ou Régner le problème (par récursivité)
3. Combiner ou Fusionner les solutions des petits problèmes pour reformer la solution du problème principal.

Trie fusion sur une liste chainées

1. Diviser

Itératif

def decoupe(lst):
  while lst is not None:
    res1 = Cellule(lst.valeur, res1)
    lst = lst.suivant
    res1, res2 = res2, res1
  return res1, res2

Récursif

def decoupe(lst, token = True):
  if lst is None:
    return None, None
  elif lst.suivant is None:
    return Cellule(lst.valeur, None)
  else:
    new = decoupe(lst.suivante, not token)
  if token:
    return Cellule(lst.valeur, new[0]), new[1]
  else:
    return new[0], Cellule(lst.valeur, new[1])

2. Régner

def fusion(lst1, lst2):
 if lst1 is None:
   return lst2
 if lst2 is None:
   return lst1 
 else:
   if lst1.valeur > lst2.valeur:
     return Cellule(lst2.valeur, fusion(lst1, lst2.suivante))
   else:
     return Cellule(lst1.valeur, fusion(lst2, lst1.suivante))

3. Combiner

def tf(lst):
  if lst is None:
    return None
  if lst.suivant is None:
    return Cellule(lst.valeur, None)
  l1, l2 = decoupe(lst)
  return fusion(tf(l1), tf(l2))

Conclusion

Le coût de la fonction trie fusion est en car on effectue des calculs en à chaque étage de l'arbre, pour étages.