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 (17:28)
From: Jon Harrop <jon@j...>
Subject: Re: [Caml-list] Set union
On Friday 25 February 2005 10:56, Radu Grigore wrote:
> 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.

Yes, my guess was O(n ln(n+N)) because the last insertions from the smaller 
set may be into a set with n+N elements. In contrast, the STL set_union 
function is T(n+N), which explains why it is so slow.

Now, what about best case behaviour: In the case of the union of two equal 
height, distinct sets, is OCaml's union T(1)?

Dr Jon D Harrop, Flying Frog Consultancy Ltd.