Discussion :

[djunityfr]

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
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

[pcaboche]

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).

[Trap D]

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"

[alexrtz]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[millie]

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 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

[PRomu@ld]

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.

[LLB]

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.

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. ^^

[pcaboche]

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...

[Jedai]

C'est parce que le langage est tellement simple et puissant qu'aucun de ses utilisateurs n'a besoin de poser de questions !!
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).

--
Jedaï