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

Algorithmes et structures de données Discussion :

calcul de complexité fonction mathematique


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé
    Inscrit en
    Mars 2006
    Messages
    87
    Détails du profil
    Informations forums :
    Inscription : Mars 2006
    Messages : 87
    Par défaut calcul de complexité fonction mathematique
    Bonjour

    Je fais un programme en Java sensé comparer differentes méthodes de calcul d'integral (rectangles, trapeze, simpson, monte carlo), et je voudrais ajouter une fonction qui compte grosso modo le nombre d'instruction effectuée par chacune des méthodes.

    Habituellement les calculs de complexité sont basés sur les operations de comparaison et d'affectation. Mais dans le cas de mon programme, est ce qu'il ne faut pas prendre en compte les multiplications, divisions, addition etc... par exemple quand l'algorithme a besoin de calculer une valeur de f(x) en un certain point.

    La fonction f(x) est donnée par l'utilisateur au debut du programme. On peut avoir une fonction dont les valeurs sont longues à calculer, comme on peut avoir f(x)=1.

    Voila un bout de code pour vous donner une idée de ce à quoi ca ressemble:

    Code C : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
    for (int i = 0; i < nbRectangles; i++) {
     
                eval = f(min + (max - min) * (2 * i + 1) / 200);
                resultat += (max - min) / nbRectangles * eval;
     
    complexite =  complexite + ?????? ;
     
            }

  2. #2
    Membre expérimenté
    Inscrit en
    Mars 2008
    Messages
    209
    Détails du profil
    Informations forums :
    Inscription : Mars 2008
    Messages : 209
    Par défaut
    la complexité d un algorithme est la somme de toutes les opérations ÉLÉMENTAIRES .
    une opération élémentaire : affectation , comparaison, addition , soustraction, multiplication , division (meme ceux dans la boucle ).

    Code C : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    for (int i = 0; i < nbRectangles; i++) {
     
                eval = f(min + (max - min) * (2 * i + 1) / 200);
                resultat += (max - min) / nbRectangles * eval;
     
            }
    complexite =  complexite + i*(1 "comparaison"+ 3 " affectations"+4 "additions''+ 2 ''multiplications'' + 2 divisions+2 soustractions)+ 2 ;

  3. #3
    Membre confirmé
    Inscrit en
    Mars 2006
    Messages
    87
    Détails du profil
    Informations forums :
    Inscription : Mars 2006
    Messages : 87
    Par défaut
    ok, mais quand on ne sait pas de quoi va avoir l'air la fonction entrée par l'utilisateur... comment faire?

    Si l'utilisateur entre f(x) = x... on sait qu'à chaque boucle, le calcul de la fonction ne demandera qu'une seule operation.

    Par contre si c'est ln(cos(x^6-Pi)) ??

  4. #4
    Membre expérimenté
    Inscrit en
    Mars 2008
    Messages
    209
    Détails du profil
    Informations forums :
    Inscription : Mars 2008
    Messages : 209
    Par défaut
    l' évaluation d 'une fonction étant un nombre constant d'opération tu peux prendre f(x) pour une opération élémentaire.

  5. #5
    Membre confirmé
    Inscrit en
    Mars 2006
    Messages
    87
    Détails du profil
    Informations forums :
    Inscription : Mars 2006
    Messages : 87
    Par défaut
    ah oui en effet, bonne idée...

    Du coup, à la fin de la comparaison des algorithmes je pourrais dire que chacun a eu besoin de :

    x + y*constante_f operations

    en prenant constante_f ce nombre constant d'operations qu'il faut pour evaluer f

Discussions similaires

  1. Calcul de complexité sur fonction Caml
    Par Al PiGiNo dans le forum Mathématiques
    Réponses: 1
    Dernier message: 09/10/2011, 13h03
  2. les fonctions mathematiques sous oracle
    Par sylab_ dans le forum Oracle
    Réponses: 3
    Dernier message: 30/01/2007, 13h19
  3. chaine de caracteres decrivant une fonction mathematique
    Par jpdar dans le forum Mathématiques
    Réponses: 8
    Dernier message: 23/12/2005, 02h53
  4. Réponses: 3
    Dernier message: 21/12/2005, 11h55
  5. [Maths] Fonctions Mathématiques
    Par Celphys dans le forum API standards et tierces
    Réponses: 1
    Dernier message: 05/07/2005, 08h44

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