Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 5 sur 5

Discussion: Problème avec les O

  1. #1
    Invité de passage
    Inscrit en
    novembre 2012
    Messages
    1
    Détails du profil
    Informations forums :
    Inscription : novembre 2012
    Messages : 1
    Points : 3
    Points
    3

    Par défaut Problème avec les O

    Hello le forum,

    on a vu les O l'an dernier et on a vu que sa permet de classer les algos. On a vu que O(log n) c'est mieux que O(nlogn) qui est mieux O(n) etc ... log c'est mieux lineaire mieux que polynomial mieux qu'exponentiel. mais dans le cours je vien de voir que O(3^n) c'est pire que O(2^n) pourtant c'est de l'exponentiel et je comprend pas. Vous pouver m'aidé a comprendre stp

  2. #2
    Expert Confirmé

    Homme Profil pro Fred Kwariz
    Chef de projet en SSII
    Inscrit en
    octobre 2011
    Messages
    887
    Détails du profil
    Informations personnelles :
    Nom : Homme Fred Kwariz
    Âge : 42
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet en SSII
    Secteur : Conseil

    Informations forums :
    Inscription : octobre 2011
    Messages : 887
    Points : 3 274
    Points
    3 274

    Par défaut

    Bonjour,

    tu trouves ça plus choquant que O(n³) «est pire» que O(n²) pourtant O(n²) comme O(n³) «c'est du polynomial» ?

  3. #3
    Membre Expert
    Homme Profil pro
    Chercheur
    Inscrit en
    mars 2010
    Messages
    1 204
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Chercheur

    Informations forums :
    Inscription : mars 2010
    Messages : 1 204
    Points : 1 645
    Points
    1 645

    Par défaut

    Salut,

    il faudrait savoir ce que tu entends par "mieux que" et "pire que". Formellement, ça veut dire quoi? A mon avis, ton problème vient du fait que tu as une vision beaucoup trop qualitative de la notation O.

  4. #4
    Rédacteur/Modérateur
    Avatar de pseudocode
    Homme Profil pro Xavier Philippeau
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    9 960
    Détails du profil
    Informations personnelles :
    Nom : Homme Xavier Philippeau
    Âge : 41
    Localisation : France, Hérault (Languedoc Roussillon)

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

    Informations forums :
    Inscription : décembre 2006
    Messages : 9 960
    Points : 15 759
    Points
    15 759

    Par défaut

    Citation Envoyé par xanderj Voir le message
    on a vu les O l'an dernier et on a vu que sa permet de classer les algos. On a vu que O(log n) c'est mieux que O(nlogn) qui est mieux O(n) etc ... log c'est mieux lineaire mieux que polynomial mieux qu'exponentiel. mais dans le cours je vien de voir que O(3^n) c'est pire que O(2^n) pourtant c'est de l'exponentiel et je comprend pas. Vous pouver m'aidé a comprendre stp
    Je n'aime pas trop la terminologie "mieux/pire", je préfère "est dominé par/ domine". voila ce qu'on pourrait dire:

    • f=O(g) <==> f est dominé par g <==> limite{ f/g } = 0
    • g=O(f) <==> f domine g <==> limite{ f/g } = +oo
    • f~g <==> f est équivalent à g <==> limite{ f/g } = Constante non-nulle



    lim { 3^n / 2^n } = lim { (3/2)^n } = +oo
    <==> 3^n domine 2^n
    <==> 2^n = O(3^n)
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Expert Confirmé

    Homme Profil pro Fred Kwariz
    Chef de projet en SSII
    Inscrit en
    octobre 2011
    Messages
    887
    Détails du profil
    Informations personnelles :
    Nom : Homme Fred Kwariz
    Âge : 42
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet en SSII
    Secteur : Conseil

    Informations forums :
    Inscription : octobre 2011
    Messages : 887
    Points : 3 274
    Points
    3 274

    Par défaut

    Citation Envoyé par pseudocode Voir le message
    Je n'aime pas trop la terminologie "mieux/pire", je préfère "est dominé par/ domine". voila ce qu'on pourrait dire:

    • f=O(g) <==> f est dominé par g <==> limite{ f/g } = 0
    • g=O(f) <==> f domine g <==> limite{ f/g } = +oo
    • f~g <==> f est équivalent à g <==> limite{ f/g } = Constante non-nulle



    lim { 3^n / 2^n } = lim { (3/2)^n } = +oo
    <==> 3^n domine 2^n
    <==> 2^n = O(3^n)
    Bonjour,

    Les limites aident mais l'équivalence n'a lieue que quand la limite vaut 1. Si la limite converge vers une constante non nulle on peut juste dire que f∈O(g) et g∈O(f). Cela pourrait se résumer en :

    • lim f/g = ∞ alors g∈O(f) et f∉O(g)
    • lim f/g = a>0 alors g∈O(f) et f∈O(g)
    • lim f/g = 0 alors g∉O(f) et f∈O(g)

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •