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é


Sujet :

Algorithmes et structures de données

  1. #1
    Membre habitué
    Profil pro
    Inscrit en
    Avril 2006
    Messages
    296
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2006
    Messages : 296
    Points : 144
    Points
    144
    Par défaut Calcul de complexité
    Bonjour

    J'ai fait un algorithme et je comprend pas comment calculer la
    complexité de celui-ci. En effet il y a des fonctions récursives
    donc si je comprend bien il y aura une complexité max ou la récursivité sera
    infini ( il y aura toujours des taches) et une complexité minimale ou il y aura qu'une tache. comment montrer la complexité mathématiquement ?

    voici la tête de l'algo

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
     
    // Algorithme
     
    Debut
     
    	type tache{
    		nom;
    		tabPrec[];
    		tabSuiv[];
    		dateTot;
    		dateTard;
    		}
     
     
    }
     
     
    //fonction qui calcul la date au plus tot
     
    fonction recurTot (tache)
    {
     
    	dateTOT <- valeurMaxMax(tache.tabPrec.dateTot) + valeur;
     
    	pour chaque tab dans tabSuiv
    		{
    		recurTot (tab)
    		}
     
    }
     
    //fonction qui calcul la date au plus tard
     
    fonction recurTard (tache){
     
     
    	dateTard<-Min(tache.tabSuiv.dateTard) + valeur;
     
    	pour chaque tab dans tabPrec
    		{
    		recurTard (tab);
    		}
    }
     
     
    //fonction qui calcul le chemin critique
     
    function cheminCrit ()
    {
    	pour chaque uneTache dans taches
    	{
    		si (uneTache.dateTot == uneTache.dateTard)
     
    			// on ajoute la tache dans le chemin critique	
    			cheminCrit.add (uneTache);
    		Fin si	
     
    	}
    }
     
     
    Fin algo
    En gros l'algo permet de calculer les dates au plus tot et tard... d'un graphe
    "potentiel métra"
    Merci pour vos réponses

  2. #2
    Expert éminent
    Avatar de PRomu@ld
    Homme Profil pro
    Ingénieur de Recherche
    Inscrit en
    Avril 2005
    Messages
    4 155
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Vienne (Poitou Charente)

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2005
    Messages : 4 155
    Points : 6 486
    Points
    6 486
    Par défaut
    En fait, l'dée pour calculer une complexité d'un algorithme récursif, c'est d'avoir une relation de récurrence sur la complexité de l'algorithme lui même.

    Pour un graphe, si celui ci est infini, ça va poser des problèmes. En revanche si celui ci est fini et que le nombre d'arrête l'est aussi ça doit pouvoir passer.

    Par contre, je n'ai pas tout suivi dans ton code.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    fonction recurTot (tache)
    {
     
    	dateTOT <- valeurMaxMax(tache.tabPrec.dateTot) + valeur;
     
    	pour chaque tab dans tabSuiv
    		{
    		recurTot (tab)
    		}
     
    }
    Tab c'est un noeud de ton graphe ? tabSuiv c'est sa liste d'adjacence ?

  3. #3
    Membre habitué
    Profil pro
    Inscrit en
    Avril 2006
    Messages
    296
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2006
    Messages : 296
    Points : 144
    Points
    144
    Par défaut
    Merci pour ta réponse j'ai finalement essayé d'évaluer la complexité a vu de nez
    parce que c'est pas évident

    Mais sinon Tab ça correspondait bien a un noeud de mon graphe et tabsuiv c'était ceux qui s'y attachait

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Calculer la complexité d'un algorithme
    Par soussou80 dans le forum Algorithmes et structures de données
    Réponses: 34
    Dernier message: 02/11/2014, 20h53
  2. Calcul de complexité
    Par zizo08 dans le forum MATLAB
    Réponses: 13
    Dernier message: 25/11/2008, 21h43
  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. calcul de complexité itératif ou algorithmique
    Par miltone dans le forum Algorithmes et structures de données
    Réponses: 13
    Dernier message: 08/04/2008, 19h38
  5. calcul de complexité
    Par an1981 dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 10/02/2008, 16h26

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