1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2018
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Côte d'Ivoire

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2018
    Messages : 3
    Points : 1
    Points
    1

    Par défaut Calculer une complexité

    Bonjour j'ai quelques difficultés en complexité. je voudrais savoir comment calculer la complexité de la fonction suivante:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    fonction devine1(ch,chaine) :
           si longueur(ch) > longueur(chaine) :
                 retourner Faux
           pour i allant de 0 à longueur(chaine) – longueur(ch) :
                 j <- 0
                 tant que j < longueur(ch) et ch[j] = chaine[i+j] :
                            j <- j+1
                            si j = longueur(ch) :
                                    retourner i
            retourner rien

  2. #2
    Expert éminent Avatar de BufferBob
    Profil pro
    responsable R&D vidage de truites
    Inscrit en
    novembre 2010
    Messages
    2 424
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : responsable R&D vidage de truites

    Informations forums :
    Inscription : novembre 2010
    Messages : 2 424
    Points : 6 485
    Points
    6 485

    Par défaut

    salut,

    de ce que j'ai pu comprendre de la notion de complexité, les traitements uniques ne sont pas pris en compte, le if ici ne change pas radicalement le déroulé de la fonction, et finalement ce qui est vraiment gourmand en temps c'est la boucle for, laquelle dépend des paramètres passés à la fonction, donc sauf erreur je dirais qu'on est face à une complexité en O(n)
    Avant donc que d'écrire, apprenez à penser.
    Selon que notre idée est plus ou moins obscure, l'expression la suit, ou moins nette, ou plus pure.
    Ce que l'on conçoit bien s'énonce clairement, et les mots pour le dire arrivent aisément.
                                                        - Nicolas Boileau, L'Art poétique

  3. #3
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2018
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Côte d'Ivoire

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2018
    Messages : 3
    Points : 1
    Points
    1

    Par défaut

    c'est quoi le n

    Je tiens à rappeler la boucle tant que est imbriquée dans la boucle for

  4. #4
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 661
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 661
    Points : 3 467
    Points
    3 467

    Par défaut

    Le n, c'est a priori la longueur de la 2ème chaine (celle qui s'appelle chaine dans le code, et qui est a priori la plus longue)

    Et quand Bufferbob dit que la complexité est en O(n), ça veut dire que si on lance plein de fois cette procédure avec des chaines de 10000 caractères, on va avoir un certain temps de traitement, Si on relance la même procédure plein de fois, avec des chaines de 20000 caractères, on aura un nouveau temps de traitement, et O(n), ça veut dire : quand je multiplie la longueur des chaines par 2, le temps de traitement se multiplie aussi par 2.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  5. #5
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2018
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Côte d'Ivoire

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : janvier 2018
    Messages : 3
    Points : 1
    Points
    1

    Par défaut

    Moi je pensais plutôt que sa complexité était O(nN) où n et N sont les longueurs des deux chaines

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 049
    Points : 15 677
    Points
    15 677

    Par défaut

    Citation Envoyé par nehm33 Voir le message
    Moi je pensais plutôt que sa complexité était O(nN) où n et N sont les longueurs des deux chaines
    Oui, c'est cela.

    L'algo fera au maximum (N-n)*n comparaisons de caractères.
    C'est l'implémentation naïve de l'algo pour la fonction strstr().
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  7. #7
    Expert éminent Avatar de BufferBob
    Profil pro
    responsable R&D vidage de truites
    Inscrit en
    novembre 2010
    Messages
    2 424
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : responsable R&D vidage de truites

    Informations forums :
    Inscription : novembre 2010
    Messages : 2 424
    Points : 6 485
    Points
    6 485

    Par défaut

    Citation Envoyé par nehm33 Voir le message
    Je tiens à rappeler la boucle tant que est imbriquée dans la boucle for
    oui, bizarrement je l'ai complètement loupée cette boucle imbriquée ce matin, les yeux qui fatiguent peut-être..

    par ailleurs on me dit "normalement on dirait O(n m), mais comme m est borné par n, O(n²) c'est correct", mais je ne suis pas à même de déterminer si c'est valide ou non par rapport à la réponse de pseudocode
    Avant donc que d'écrire, apprenez à penser.
    Selon que notre idée est plus ou moins obscure, l'expression la suit, ou moins nette, ou plus pure.
    Ce que l'on conçoit bien s'énonce clairement, et les mots pour le dire arrivent aisément.
                                                        - Nicolas Boileau, L'Art poétique

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

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 049
    Points : 15 677
    Points
    15 677

    Par défaut

    Citation Envoyé par BufferBob Voir le message
    par ailleurs on me dit "normalement on dirait O(n m), mais comme m est borné par n, O(n²) c'est correct", mais je ne suis pas à même de déterminer si c'est valide ou non par rapport à la réponse de pseudocode
    m n'est pas "borné" par n, puisque ce sont deux variables libres. On peut y mettre ce qu'on veut.

    C'est vrai que si m>n alors l'algo retourne FAUX directement et donc est O(1).
    Dans les autres cas, il est O(nm) avec m<=n, et donc O(n²)

    Mathématiquement, O() désigne une domination asymptotique.
    Donc si un algo est O(n), il est aussi O(n²), O(n^3), O(n.log(n)), ... et n'importe quoi plus grand que "n".

    Généralement, on cherche plutot à fournir Theta() qui désigne un équivalence asymptotique.
    Mais comme c'est mathématiquement compliqué, on se limite a fournir le plus "petit" O() parmi les complexités usuelles
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  9. #9
    Expert éminent Avatar de BufferBob
    Profil pro
    responsable R&D vidage de truites
    Inscrit en
    novembre 2010
    Messages
    2 424
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : responsable R&D vidage de truites

    Informations forums :
    Inscription : novembre 2010
    Messages : 2 424
    Points : 6 485
    Points
    6 485

    Par défaut

    merci de cette précision
    Avant donc que d'écrire, apprenez à penser.
    Selon que notre idée est plus ou moins obscure, l'expression la suit, ou moins nette, ou plus pure.
    Ce que l'on conçoit bien s'énonce clairement, et les mots pour le dire arrivent aisément.
                                                        - Nicolas Boileau, L'Art poétique

  10. #10
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 661
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 661
    Points : 3 467
    Points
    3 467

    Par défaut

    Citation Envoyé par BufferBob Voir le message
    oui, bizarrement je l'ai complètement loupée cette boucle imbriquée ce matin, les yeux qui fatiguent peut-être..
    Ce matin, le code était très difficile à lire, parce qu'il n'y avait pas la balise code. Et donc pas d'indentation en particulier.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

Discussions similaires

  1. Réponses: 24
    Dernier message: 30/10/2012, 15h23
  2. Réponses: 7
    Dernier message: 05/07/2005, 17h50
  3. methode qui calcul une moyenne du traffic
    Par siry dans le forum Développement
    Réponses: 7
    Dernier message: 05/05/2005, 18h16
  4. Calculer une duree entre 2 dates
    Par d.w.d dans le forum C++
    Réponses: 7
    Dernier message: 02/03/2005, 23h39
  5. calculer une moyenne avec une requete externe
    Par allowen dans le forum Langage SQL
    Réponses: 3
    Dernier message: 27/01/2005, 17h02

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