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
[Caml-list] Set and Map question
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-09-20 (03:56)
From: skaller <skaller@u...>
Subject: Re: [Caml-list] Re: Set and Map question
On Mon, 2004-09-20 at 13:14, Seth Fogarty wrote:

> What I MEANT to ask is: Is there a O(n) method of set/map construction
> from a list, as opposed to the O(n log n) fold method.

It seems to me that in general that is impossible,
since random tree insertions are at least O(log n)
in the tree size (proportional to depth).

Perhaps you meant, assuming the list is sorted?
In that case, in theory you could precalculate
the shape of the tree just from the size, and then
fill in the elements in O(n).

John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners