[OCaml] Complexité et temps d'exécution

Salut à tous,
comme à chaque fois que j'ai eu un problème il a été réglé en deux coups de cuillère à pot grace à vos réponses, je me tourne une nouvelle fois vers vous :P
J'ai codé deux fonctions en Caml, et j'aimerais connaître leur complexité et temps d'exécution... Seulement voilà, je ne sais pas du tout comment faire... :?
Voici les fonctions :
- Calcul du n-ième terme de Fibonacci en récursif
- Même chose en impératif
Si vous pouviez m'expliquer la complexité (et comment calculer cette complexité...) ne serait-ce que d'une fonction, ça m'aiderait beaucoup pour la suite :-)
Merci d'avance, bonne soirée à tous,
bye

Pourrais-tu nous donner le code de tes 2 fonctions afin que nous puissions répondre, stp?

Ceci est un cas d'école: l'une des deux fonctions devrait normalement avoir une complexité en O(n) alors que l'autre (mal programmée) devrait avoir une complexité en O(n^2).

Il serait intéressant que tu consultes cette page http://www-id.imag.fr/Laboratoire/Me...urs/node6.html

Tu voulais sans doute dire en "itératif" et non pas "impératif" :lol:

Salut,

Complexité de Fibonacci en récursif : http://www.lirmm.fr/~bodini/CAA/coursCAAC4.pdf

Pour l'itératif, c'est du o(n).

Calcul de temps en Caml avec enregistrement dans un fichier :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

let test fichier = let f = open_out fichier and n = ref 0 in while !n <= 50 do t1 = Unix.times () in fonction_a_tester n; let t2 = Unix.times () in Printf.fprintf f "%d %e\n" !n (t2.Unix.tms_utime -. t1.Unix.tms_utime); n := !n + 5 done; close_out f;;

---

où n est ce qui doit faire augmenter le temps (par exemple le rang dans Fibonacci).

Chaque ligne du fichier de sortie est de la forme :
n temps
ce qui permet de tracer facilement des courbes avec xgraphic ou autre.

Citation:

---

Envoyé par pcaboche

Ceci est un cas d'école: l'une des deux fonctions devrait normalement avoir une complexité en O(n) alors que l'autre (mal programmée) devrait avoir une complexité en O(n^2).

---

Oui, mais j'espère qu'il djunityfr ne l'a pas codé comme ça. OCaml est beaucoup plus joli en récursif, et avoir une complexité linéaire en récursif est très simple. Pour peu que ce soit terminal, ce sera au moins aussi rapide que l'itératif.

Citation:

---

Si vous pouviez m'expliquer la complexité (et comment calculer cette complexité...) ne serait-ce que d'une fonction, ça m'aiderait beaucoup pour la suite :-)

---

La question à se poser, c'est : combien de fois il faut "boucler" pour calculer fibo n ?


Edit : j'avais pas vu la date. Je pensais que ce forum était plus vivant. ^^

Citation:

---

Envoyé par LLB

Edit : j'avais pas vu la date. Je pensais que ce forum était plus vivant. ^^

---

En même temps, on ne reçoit pas énormément de questions concernant Caml...

C'est parce que le langage est tellement simple et puissant qu'aucun de ses utilisateurs n'a besoin de poser de questions !! :roll:
Blague à part, c'est sans doute parce que les gens qui ont une question cherchent un forum OCaml et ne le trouve pas (la principale raison restant bien sûr la quantité fort restreinte de programmeurs OCaml, surtout passant sur Developpez.com qui est à vocation professionnelle, ce qui explique qu'on ait pas de forum OCaml... cercle vicieux). :aie:

--
Jedaï

Citation:

---

Envoyé par rurouni alex

Complexité de Fibonacci en récursif : http://www.lirmm.fr/~bodini/CAA/coursCAAC4.pdf

Pour l'itératif, c'est du o(n).

---

Désolé, le post est super vieux, mais je cherchais quelque chose et je suis tombé là dessus. Je comprend pas comment ils sortent cette complexité, ils parlent de taille d'instance, mais on dirait qu'ils ont oublié qu'un entier n en machine est de taille log_2 n. Ce qui fait que toutes les complexités sont fausses :aie: A moins de considèrer que la taille de l'instance est égale à l'instance... ce qui serait suspect. A moins que ce soit pour simplifier

Ici, la complexité linéaire est en nombre de calcul. Plutôt de recalculer des termes déjà calculés, le calcul de fibo va se faire en calculant Fn et Fn+1 (ou Fn et Fn-1 suivant la méthode). Par ce fait on calcule Fn en n itérations.

En fait, j'avais craqué. Mais je peux plus revoir le lien, le serveur a l'air temporairement out.

Citation:

---

Envoyé par millie

En fait, j'avais craqué. Mais je peux plus revoir le lien, le serveur a l'air temporairement out.

---

:lol: on a cru comprendre... :aie:


en revanche, en lisant ce post, il semblerait qu'il y ait confusion entre itératif et impératif

Citation:

---

Envoyé par wikipedia

la programmation impérative est un paradigme de programmation qui décrit les opérations en termes d'états du programme et de séquences d'instructions exécutées par l'ordinateur pour modifier l'état du programme.

---

http://fr.wikipedia.org/wiki/Program...mp%C3%A9rative

on est donc sur la conception du programme...


alors qu'itérative est plus proche de la forme sous laquelle il est codé... ;)


d'ailleurs, il est possible (avec les optimisations) d'avoir un code récursif plus performant et de même complexité que le code itératif traditionnel... en raison des tail-calls, ce qui ne serait pas forcemment possible sur le code itératif qui gère trop de détails lui-même

nb: ceci est faux si les optimisations utilisent les pattern-matching, auquel cas il y aura substitution des deux codes, par un code "connu" du compilo et hyper-agressif ;)

Citation:

---

Envoyé par gorgonite

d'ailleurs, il est possible (avec les optimisations) d'avoir un code récursif plus performant et de même complexité que le code itératif traditionnel...

---

Maple intègre des mécanismes de programmation dynamique permettant d'éviter ce genre de chose. C'est à dire que si f(x) a été calculé une fois pendant la récursion. Il ne sera pas récalculé une seconde fois. Ce qui permet de rivaliser niveau vitesse :mrgreen:

Citation:

---

on a cru comprendre...

---

En fait, pour me défendre.

Si n est l'instance d'entrée, la complexité est en O(n).
Mais de manière formelle, la fonction complexité prenant en entrée la taille d'une instance est : f : n ->R est en O(exp(n)) où n, n'est plus ici l'instance, mais la taille de l'instance.

Citation:

---

Envoyé par millie

Maple intègre des mécanismes de programmation dynamique permettant d'éviter ce genre de chose. C'est à dire que si f(x) a été calculé une fois pendant la récursion. Il ne sera pas récalculé une seconde fois. Ce qui permet de rivaliser niveau vitesse :mrgreen:

---

il stocke dans une table... procédé très coûteux en mémoire, sans grand intérêt si on compile ;)