Intersection et réunion triée de listes triées

I) Présentation et objectifs

Le calcul de la réunion triée de deux listes triées est un point essentiel d'un tri très efficace (de complexité n ln(n)), le tri fusion.

  Etant données deux listes triées par ordre croissant s et t, on veut calculer les listes triées inter(s, t) = s ∩ t et union(s, t) = s ∪ t sans utiliser de fonction de tri.
  On souhaite également que les complexités de ces fonctions soient en O ( ns + nt ) , avec ns = len(s) et nt = len(t) .

Par exemple, avec s = [1, 2, 5, 5, 8, 8, 9, 10] et t = [3, 5, 6, 8, 8, 8, 11] on aura:
     inter(s, t) = [5, 8, 8] et union(s, t) =  [1, 2, 3, 5, 5, 5, 6, 8, 8, 8, 8, 8, 8, 9, 10, 11]

Le coût est ici le nombre d'affectations, de comparaisons ou d'ajout d'un élément à la fin d'une liste. On néglige les additions.

II) Etude de deux mauvais algorithmes

1) Intersection

def inter_1(s,t):
   """ liste triée intersection des listes s et t triées"""
    ns, nt = len(s), len(t)
    res = []
    for k in range(ns):
        e = s[k]
        for j in range(nt):
            if t[j] == e:
                res.append(e)
    return res

Q1) Calculer inter_1(s,t) avec s = [1, 2, 5, 5, 8, 8, 9, 10] et t = [3, 5, 6, 8, 8, 8, 11]

Q2) A quelles conditions sur les listes s et t cette fonction inter_1(s, t) donne-t-elle le bon résultat ?

Q3) Calculer son coût au pire  et en déduire que sa complexité est C 1 ( s , t ) en O ( ns nt ) .

2) Réunion

def reunion_1(s,t):
    """ liste triée réunion des listes s et t triées"""
    return sorted(s + t)

Q4) Expliquer cette fonction et justifier qu'elle résout le problème.

Q5) Quelle propriété des listes s et et cette fonction n'exploite-t-elle pas ?

Q6) Calculer sa complexité en fonction de ns = len(s) et de nt = len(t). On rappelle que le tri effecué par la méthode sort() ou la fonction sorted() d'une liste de n éléments a une complexité de n×ln(n).
Vérifier que cette complexité n'est pas conforme à l'objectif O ( ns + nt ) .

III) Proposition d'algorithmes corrects et efficaces

1) Intersection

Pour calculer la liste res = s ∩ t :

    • on se place au début de la liste t

    •• on parcourt la liste s et pour chaque élément e de la liste s, on avance dans la liste t jusqu'à (si c'est possible) trouver un élément e'=t[j] de t tel que  e' ≥ e:

        (1)  si e' = e, alors on ajoute e à res et on repart de l'élément qui suit e' en avançant dans t

         (2)  si e' > e, on repart de e' en avançant dans t

         (3)  si e' n'existe pas, c'est fini (mais on peut aussi terminer le parcours de la liste s)

2) Réunion

On s'inspire de l'idée précédente:

Pour calculer la liste res = s ∪ t :

    • on se place au début de la liste t
    •• on parcourt la liste s et pour chaque élément e de la liste s, on avance dans la liste t en ajoutant à la liste res tous les éléments e' de t avec e' ≤ e.
Puis on ajoute e et on passe à l'élément suivant de s en repartant de l'élément suivant de la liste t.
    ••• à la fin on n'oublie pas les éventuels éléments restants de la liste t.

IV) Algorithmes

Q7) Ecrire une fonction inter(s, t) (avec s et t deux listes triées par ordre croissant) calculant la liste triée s ∩ t en suivant les consignes précédentes.

Q8) Ecrire une fonction union(s, t) (avec s et t deux listes triées par ordre croissant) calculant la liste triée s ∪ t en suivant les consignes précédentes.

V) Complexité

On note, pour k ∈ {0,..., ns - 1}, j k l'indice de l'élément e ' = t [ j k ] entier à partir duquel on avance dans la liste t afin de trouver un éventuel élément e'= t[j] de la liste t supérieur ou égal à e = t[k].
On aura j k = nt si la liste t est épuisée et qu'aucun élément e' = t[j] n'a pu être trouvé.
On pose j ns = j ns - 1

Q9) Pour les listes s et t de l'exemple du I), calculer la suite ( j k ) k { 0 , ... , ns } .

Q10) Prouver que le coût au pire de la fonction inter(s, t) est majoré par 4 + Σ k = 0 ns - 1 ( 7 + 3 ( j k + 1 - j k ) ) et en déduire que la complexité C inter ( s , t ) de la fonction inter(s, t) est en O(ns+nt) .

Q11) Majorer le coût au pire de la fonction union(s, t) et justifier que la complexité C union ( s , t ) de la fonction union(s, t) est en O ( ns + nt ) .

© 2014 - Eric Obermeyer      Powered by      Corrigé