Discussion :

[Al PiGiNo]

Bien le bonjour,
je suis actuellement en Licence 3 d'informatique, et venant d'un DUT Sérécom, j'ai un peu de mal avec les mathématiques discrètes.

Voilà mon problème :

On a la fonction

Code :

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

1
2
3
4
#let rec wait = fun
0 -> 1.
|n -> sqrt(wait(n-1));;
wait : int -> float = <fun>

Je dois donc calculer la complexité de la fonction wait.
J'ai fais plusieurs test et elle renvoie toujours 1. (normal jusque là) et lorsque l'on écrit 1000000 elle est Out_Of_Memory.

Je comprend pas bien comment marche cette fonction a part qu'elle renvoie les racines. Et comment commencer le calcul de complexité ...

Si vous pouviez m'aiguiller, j'en serais très reconnaissant.

[pseudocode]

Je ne sais pas trop quel est le langage utilisé, mais on dirait que c'est une fonction définie par :

Wait(0)=1
wait(n) = sqrt(wain(n-1)), avec n >0

Auquel cas, on peut simuler assez vite son comportement

wait(3) = sqrt(wait(2)) = sqrt(sqrt(wait(1))) = sqrt(sqrt(sqrt(wait(0)))) = sqrt(sqrt(sqrt(1)))

Bref, pour calculer wait(N) il faut N appels récursifs. Donc une complexité O(N)

J'ai fais plusieurs test et elle renvoie toujours 1. (normal jusque là) et lorsque l'on écrit 1000000 elle est Out_Of_Memory.

Lorsque N est très grand, ton programme fait beaucoup d'appels récursifs et la pile d'appel doit saturer à un moment.