Une opération supplémentaire, l'union d'ensemble

On souhaite ajouter une opération d’union sur les ensembles:

set__union: set * set -> set

set__union(set__empty, s)       = s
set__union(set__add(s, c), s')  = set__add(set__union(s, s'), c)

Opération externe

On propose l’algorithme suivant basé sur les opérations du TAD:

function set__union(s1, s2) returns (s3):
    s3 = set__empty();
    for i in 0..INT_MAX // stored values of type int
        if (set__find(s1, i) or set__find(s2, i))
            s3 = set__add(s3, i)

Calculer la complexité de cet algorithme pour les deux mises en œuvre de set.

Opération interne

Au vu de la complexité de l’opération externe, on propose plutôt de mettre en œuvre set__union comme une opération interne du TAD. Il est donc possible d’utiliser la représentation mémoire de struct set pour une plus grande efficacité.

Donner un algorithme de complexité linéaire pour cette opération dans l’une des deux mises en œuvre du type struct set. On choisira le prototype ci-dessous où la fonction prend en paramètre deux struct set, et renvoie un nouveau struct set qui contient l’union de ses deux paramètres.

struct set * set__union(const struct set * s1, const struct set * s2);