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 :

Complexité pire-cas et meilleur-cas de mon algo


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éclairé Avatar de sorry60
    Profil pro
    Inscrit en
    Octobre 2003
    Messages
    802
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2003
    Messages : 802
    Par défaut Complexité pire-cas et meilleur-cas de mon algo
    Salut

    J'ai écrit un algo itératif qui donne la plus grande séquence de 1 dans un tableau à 1 dimension contenant des 0 et des 1.
    Le voici :

    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
     
    fonction maxSeq1(T,i,j)
       p <- 0 // position de la plus grande sequence de 1
       n <- 0 // longueur de la plus grande sequence de 1
       b <- 0 // longueur de la sequence courante de 1
     
       pour k de i à j faire
          si T[k] = 0 alors
             b <- 0
          sinon
             b <- b + 1
             si b > n alors
                p <- k - b + 1
                n <- b
             finSi
          finSi
       finPour
       retourner (p,n)
    finFonction
    Je dois trouver la complexité pire-cas et meilleur cas de cet algo.

    J'ai trouvé : complexité pire-cas = complexité meilleur-cas = j - i + 1 (nombre de fois qu'on passe dans le pour etant donné que le reste est en o(1)).

    Ma question est simple : ai je bon ?
    Merci à vous

  2. #2
    Expert confirmé
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Par défaut
    Citation Envoyé par sorry60
    Ma question est simple : ai je bon ?
    D'après toi ? Faut avoir un peu confiance en toi !! Si tu viens nous demander à chaque question de ton exercice si tu as bon ou pas....

    --
    Jedaï

  3. #3
    Membre éclairé Avatar de sorry60
    Profil pro
    Inscrit en
    Octobre 2003
    Messages
    802
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2003
    Messages : 802
    Par défaut
    Lol oui je pense avoir bon, mais vu que l'algo n'est pas mon fort (c'est la 1ere année où je cherche des complexités), je préfère être sur...

    Enfin en etant logique, il n'y a qu'une boucle pour, dans laquelle on fait (j - i + 1) opérations, peu importe la taille du tableau..donc pour moi le pire cas et le meilleur cas sont egaux

  4. #4
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Par défaut
    Bonjour,

    tu n'as qu'une seule boucle qui n'appelle aucune fonction ni aucune instruction particulière, rien que des tests.

    Donc d'après toi :
    - combien de fois passes tu dans ta boucle ?
    - quel serait le pire des cas ?
    - quel serait le meilleur des cas ?
    - Quelle complexité en déduis tu si la boucle fais N itérations ?
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  5. #5
    Membre Expert Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 55

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Par défaut
    j'ai enseigné de nombreuses années, et franchement, c'est le genre d'exercice à la con. On peut trouver mieux pour expliquer "l'interet" de la determination du pire cas...

  6. #6
    Membre éclairé Avatar de sorry60
    Profil pro
    Inscrit en
    Octobre 2003
    Messages
    802
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2003
    Messages : 802
    Par défaut
    Citation Envoyé par ToTo13
    Bonjour,

    tu n'as qu'une seule boucle qui n'appelle aucune fonction ni aucune instruction particulière, rien que des tests.

    Donc d'après toi :
    - combien de fois passes tu dans ta boucle ?
    - quel serait le pire des cas ?
    - quel serait le meilleur des cas ?
    - Quelle complexité en déduis tu si la boucle fais N itérations ?
    - combien de fois passes tu dans ta boucle ? (j-i+1) fois
    - quel serait le pire des cas ? j = N
    - quel serait le meilleur des cas ? j = i
    - Quelle complexité en déduis tu si la boucle fais N itérations ? pire-cas : o(N), meilleur-cas : o(1)

    non ?

  7. #7
    Membre expérimenté
    Profil pro
    Inscrit en
    Janvier 2004
    Messages
    192
    Détails du profil
    Informations personnelles :
    Âge : 44
    Localisation : France

    Informations forums :
    Inscription : Janvier 2004
    Messages : 192
    Par défaut
    Quelle complexité en déduis tu si la boucle fais N itérations ? pire-cas : o(N), meilleur-cas : o(1)
    La taille des données en entrée n'est pas N, mais j-i+1. La distribution de i et j n'a rien à voir avec la complexité de la procédure...

  8. #8
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Par défaut
    Citation Envoyé par sorry60
    - combien de fois passes tu dans ta boucle ? (j-i+1) fois
    - quel serait le pire des cas ? j = N
    - quel serait le meilleur des cas ? j = i
    - Quelle complexité en déduis tu si la boucle fais N itérations ? pire-cas : o(N), meilleur-cas : o(1)

    non ?

    Ta première intuition était la bonne (donc celle que je viens de citer est fausse). Je te signale que ce n'est pas des o mais des O (c'est totalement différent).
    J'ai trouvé : complexité pire-cas = complexité meilleur-cas = j - i + 1 (nombre de fois qu'on passe dans le pour etant donné que le reste est en o(1)).

    J'ai écrit un algo itératif qui donne la plus grande séquence de 1 dans un tableau à 1
    Je ne comprends donc pas pourquoi tu fais intervenir i et j, tu pourrais passer en paramètre le tableau (i serait égal à 1 et j à la taille du tableau).

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

Discussions similaires

  1. Schématiser tout les cas de figure possibles dans un algo
    Par Lekno dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 15/03/2015, 14h11
  2. le meilleur SGBD pour mon cas ?
    Par nelmehdi dans le forum Décisions SGBD
    Réponses: 3
    Dernier message: 02/04/2010, 16h10
  3. Bug dans mon algo..
    Par Chekov dans le forum Langage
    Réponses: 3
    Dernier message: 30/06/2006, 20h42
  4. Correction de mon algo
    Par Shakan972 dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 27/01/2006, 18h40
  5. Perplexité face au résulat de mon algo ...qu'en pensez vous?
    Par Clad3 dans le forum Algorithmes et structures de données
    Réponses: 5
    Dernier message: 14/06/2005, 15h15

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