From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id VAA01160 for caml-redistribution; Thu, 9 Oct 1997 21:17:53 +0200 (MET DST)
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id KAA17021 for <caml-list@pauillac.inria.fr>; Thu, 9 Oct 1997 10:33:31 +0200 (MET DST)
Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35])
	by concorde.inria.fr (8.8.7/8.8.5) with ESMTP id KAA17128;
	Thu, 9 Oct 1997 10:33:28 +0200 (MET DST)
Received: (from xleroy@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id KAA17017; Thu, 9 Oct 1997 10:33:28 +0200 (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)
Cc: caml-list@inria.fr
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Sender: weis

> 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