* Ocaml: module Map
@ 1997-10-02 15:23 Dalila Bakir - Limav
1997-10-09 8:33 ` Xavier Leroy
0 siblings, 1 reply; 2+ messages in thread
From: Dalila Bakir - Limav @ 1997-10-02 15:23 UTC (permalink / raw)
To: caml-list
Bonjour,
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"?. Plus pre'cise'ment, si
j'utilise "fold" pour rechercher la valeur maximale de la cle', la
comple'xite' serait-elle la me^me?
Dalila.
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: Ocaml: module Map
1997-10-02 15:23 Ocaml: module Map Dalila Bakir - Limav
@ 1997-10-09 8:33 ` Xavier Leroy
0 siblings, 0 replies; 2+ messages in thread
From: Xavier Leroy @ 1997-10-09 8:33 UTC (permalink / raw)
To: Dalila Bakir - Limav; +Cc: caml-list
> 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
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~1997-10-09 19:17 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
1997-10-02 15:23 Ocaml: module Map Dalila Bakir - Limav
1997-10-09 8:33 ` Xavier Leroy
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox