English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Set union
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2005-02-25 (10:56)
From: Radu Grigore <radugrigore@g...>
Subject: Re: [Caml-list] Set union
On Thu, 24 Feb 2005 09:20:04 +0000, Jon Harrop <jon@jdh30.plus.com> wrote:
> Following my last post about the speed of set union in OCaml compared to
> C++/STL. What is the complexity of set union in OCaml in terms of the number
> of elements and the number of comparisons?

As no one gave an informed answer I'll risk a hand-waiving one.

When all elements of a set are bigger than all elements of the other
set the Set.union function seems to simply add the elements of the
small set to the bigger set one at a time. So the complexity looks
like O(m lg n) where m is the size of the smaller set. For other cases
the process is a bit more complex: take the root of the short tree,
split the large tree into smaller/larger elements based on that root,
compute union of "small" trees, "compute union of "large" trees",
merge them. If I'm not mistaken this is O(m lg n) too.