Ben n'utilise pas un langage qui te faire croire ça pour un système dont tu veux prouver la fiabilité.
> Remarque : une fonction de complexité linéaire en l'entrée qui mettrait le meme
> temps que fibo sur l'entree 1 mettra egalement le meme temps certain sur
> l'entree 277887173.
Je comprends pas ce que tu veux dire. Fibo non optimisé n'est justement pas linéaire (je sais pas si le compilo CAML sait optimiser ça). Le truc avec fibo, c'est que sa complexité est linéaire en fonction de sa sortie, qui elle même est a peu près une exponentielle de son entrée. Donc, si tu veux utiliser fibo sur une entrée pas trop ridiculement petite (100, j'avais peut-être été optimiste, mais essaye avec 1000 si tu veux), il te faudra des milliards d'années de calcul (ou écrire la version de complexité O(n), pas bien difficile par ailleurs).
[^] # Re: exponentiel => indecidable
Posté par Matthieu Moy (site web personnel) . En réponse au journal couverture de code. Évalué à 3.
Ben n'utilise pas un langage qui te faire croire ça pour un système dont tu veux prouver la fiabilité.
> Remarque : une fonction de complexité linéaire en l'entrée qui mettrait le meme
> temps que fibo sur l'entree 1 mettra egalement le meme temps certain sur
> l'entree 277887173.
Je comprends pas ce que tu veux dire. Fibo non optimisé n'est justement pas linéaire (je sais pas si le compilo CAML sait optimiser ça). Le truc avec fibo, c'est que sa complexité est linéaire en fonction de sa sortie, qui elle même est a peu près une exponentielle de son entrée. Donc, si tu veux utiliser fibo sur une entrée pas trop ridiculement petite (100, j'avais peut-être été optimiste, mais essaye avec 1000 si tu veux), il te faudra des milliards d'années de calcul (ou écrire la version de complexité O(n), pas bien difficile par ailleurs).