IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Mathématiques Discussion :

Calcul de complexité sur fonction Caml


Sujet :

Mathématiques

  1. #1
    Nouveau membre du Club
    Homme Profil pro
    Inscrit en
    Mai 2011
    Messages
    51
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Mai 2011
    Messages : 51
    Points : 27
    Points
    27
    Par défaut Calcul de complexité sur fonction Caml
    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.

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 084
    Points
    16 084
    Par défaut
    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.

Discussions similaires

  1. Réponses: 13
    Dernier message: 06/08/2014, 11h07
  2. [PHP 5.0] Problème sur fonction de calcul horaire
    Par mariemarie75 dans le forum Langage
    Réponses: 1
    Dernier message: 07/07/2011, 22h10
  3. calcul de complexité fonction mathematique
    Par abdelhamidem dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 16/05/2008, 14h37
  4. [langage] Pointeur sur fonction
    Par Fanch.g dans le forum Langage
    Réponses: 2
    Dernier message: 02/10/2004, 11h43
  5. Declaration de fonction retournant un pointeur sur fonction
    Par pseudokifaitladifférence dans le forum C
    Réponses: 5
    Dernier message: 11/08/2003, 20h37

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo