Version française
Home     About     Download     Resources     Contact us    
Browse thread
Ocaml: module Map
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Xavier Leroy <Xavier.Leroy@i...>
Subject: Re: Ocaml: module Map
> 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