Re: Ocaml: module Map

From: Xavier Leroy (Xavier.Leroy@inria.fr)
Date: Thu Oct 09 1997 - 10:33:28 MET DST


From: Xavier Leroy <Xavier.Leroy@inria.fr>
Message-Id: <199710090833.KAA17017@pauillac.inria.fr>
Subject: Re: Ocaml: module Map
In-Reply-To: <3433BC8B.5F93@univ-valenciennes.fr> from Dalila Bakir - Limav at "Oct 2, 97 03:23:55 pm"
To: Dalila.Bakir@univ-valenciennes.fr (Dalila Bakir - Limav)
Date: Thu, 9 Oct 1997 10:33:28 +0200 (MET DST)

> Du point de vue de la complexite, les acce's et les modifications sur
> les "Maps" sont d'ordre log(n) si n est la taille d'une "Map". Quelle
> serait la complexite de l'ope'ration "fold"?.

Map.fold parcours les n elements du dictionnaire, sa complexite est
donc au moins O(n). En fait, c'est exactement O(n) puisqu'il s'agit
d'un parcours gauche-droite d'arbre binaire.

> Plus pre'cise'ment, si
> j'utilise "fold" pour rechercher la valeur maximale de la cle', la
> comple'xite' serait-elle la me^me?

Si vous utilisez Map.fold, c'est forcement en O(n).

L'implementation sous-jacente des dictionnaires (arbres binaires
croissants equilibres) permettrait de determiner le max de la cle en
temps log(n), mais ce n'est pas une des operations exportees par le
module Map.

- Xavier Leroy



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:12 MET