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 :

Ordre de compléxité


Sujet :

Algorithmes et structures de données

  1. #1
    Membre à l'essai
    Femme Profil pro
    Étudiant
    Inscrit en
    Novembre 2011
    Messages
    16
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Algérie

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Finance

    Informations forums :
    Inscription : Novembre 2011
    Messages : 16
    Points : 16
    Points
    16
    Par défaut Ordre de compléxité
    Bonjour,
    Svp est ce qu'il y a quelqu'un qui peut me corrigé cet exercice:
    Montrer que les affirmations suivantes sont correctes:

    1) n !=O(n puissance n)
    ma solution:
    n!=1 *(n+1)*(n+2)*.....*(n)<=n*n*....*n=n puissance n.

    2)la somme de i=0 à n de i²=Θ(n puissance 3)
    ma solution:
    la somme de i=0 à n de i²=0²+1²+2²+...+n²>=n* n²=n puissance 3

    3)Et pour 5n²-6n ET 2n²+n log n=Θ(n²) je n'ai aucune idée pour prouver que c'est vrai.

    Merci d'avance.

  2. #2
    Membre expérimenté
    Homme Profil pro
    Chercheur
    Inscrit en
    Mars 2010
    Messages
    1 218
    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 218
    Points : 1 685
    Points
    1 685
    Par défaut
    Bonjour,

    Citation Envoyé par nadia_inf Voir le message
    1) n !=O(n puissance n)
    ma solution:
    n!=1 *(n+1)*(n+2)*.....*(n)<=n*n*....*n=n puissance n.
    Ta formule de factorielle est fausse et par conséquent la majoration aussi. En reprenant la formule exacte de la factorielle, tu pourras majorer chaque facteur par n comme tu l'as fait.


    Citation Envoyé par nadia_inf Voir le message
    2)la somme de i=0 à n de i²=Θ(n puissance 3)
    ma solution:
    la somme de i=0 à n de i²=0²+1²+2²+...+n²>=n* n²=n puissance 3
    J'ai l'impression que tu as minoré chacun des termes de ta somme par n, mais cela ce n'est pas possible : on n'a pas 1>=n, 2>=n, etc. Je pense que le plus simple pour répondre à la question est de chercher la formule donnant la somme des carrés des n premiers entiers :
    http://www.les-suites.fr/somme-des-n...ers-carres.htm

    Citation Envoyé par nadia_inf Voir le message
    3)Et pour 5n²-6n ET 2n²+n log n=Θ(n²) je n'ai aucune idée pour prouver que c'est vrai.
    Je ne comprends pas l'énoncé de la question. Peux-tu développer?

  3. #3
    Membre à l'essai
    Femme Profil pro
    Étudiant
    Inscrit en
    Novembre 2011
    Messages
    16
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Algérie

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Finance

    Informations forums :
    Inscription : Novembre 2011
    Messages : 16
    Points : 16
    Points
    16
    Par défaut
    1)je pense que pour la formule de factorielle est correct: n! = 1.2.3......(n - 2).(n - 1).n

    2)pour la 2eme question c'est bon c'est fait grace au lien que vous m'avez donné.

    3)pour la derniere question :je dois montrer que les deux affirmations suivantes sont correctes:
    5n²-6n=Θ(n²)
    2n²+n log n=Θ(n²)
    Mais je ne sais comment minoré

  4. #4
    Membre expérimenté
    Homme Profil pro
    Chercheur
    Inscrit en
    Mars 2010
    Messages
    1 218
    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 218
    Points : 1 685
    Points
    1 685
    Par défaut
    Citation Envoyé par nadia_inf Voir le message
    3)pour la derniere question :je dois montrer que les deux affirmations suivantes sont correctes:
    5n²-6n=Θ(n²)
    2n²+n log n=Θ(n²)
    Mais je ne sais comment minoré
    5n²-6n>=cn² <=> 5n-6>=cn <=> (5-c)n>=6 ----> impossible pour c>0

    pour la deuxième, il faut étudier les variations de x-log(x) et procéder de façon similaire à précédemment en utilisant le résultat cette étude pour minorer log(n).

  5. #5
    Membre expert
    Avatar de kwariz
    Homme Profil pro
    Chef de projet en SSII
    Inscrit en
    Octobre 2011
    Messages
    898
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Moselle (Lorraine)

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

    Informations forums :
    Inscription : Octobre 2011
    Messages : 898
    Points : 3 352
    Points
    3 352
    Par défaut
    Citation Envoyé par Aleph69 Voir le message
    5n²-6n>=cn² <=> 5n-6>=cn <=> (5-c)n>=6 ----> impossible pour c>0

    pour la deuxième, il faut étudier les variations de x-log(x) et procéder de façon similaire à précédemment en utilisant le résultat cette étude pour minorer log(n).
    Bonsoir,

    on a quand même n² < 5n²-6n < 5n² pour n>1 donc 5n²-6n est en Θ(n²).

  6. #6
    Membre expérimenté
    Homme Profil pro
    Chercheur
    Inscrit en
    Mars 2010
    Messages
    1 218
    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 218
    Points : 1 685
    Points
    1 685
    Par défaut
    Salut,

    exact, j'ai un petit peu oublié de raisonner de façon asymptotique!

    On reprend :

    5n²-6n>=cn² <=> 5n-6>=cn <=> (5-c)n>=6 ----> impossible pour c>0
    car pour n=1, n obtient (5-c)>=6... sauf qu'il existe toujours un rang N tel que pour tout n>=N, on a bien (5-c)n>=6, quitte à fixer c dans ]0;5[!

    Merci kwariz!

  7. #7
    Membre à l'essai
    Femme Profil pro
    Étudiant
    Inscrit en
    Novembre 2011
    Messages
    16
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Algérie

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Finance

    Informations forums :
    Inscription : Novembre 2011
    Messages : 16
    Points : 16
    Points
    16
    Par défaut
    Merci beaucoup pour votre aide.

Discussions similaires

  1. [CR8] Groupes nommés par ordre spécifié
    Par PschittN dans le forum SAP Crystal Reports
    Réponses: 2
    Dernier message: 18/05/2004, 00h46
  2. ORDER BY dans un ordre inhabituel
    Par Riam dans le forum SQL Procédural
    Réponses: 2
    Dernier message: 21/03/2003, 14h29
  3. Question : ordre des bits ?
    Par Choupi dans le forum C
    Réponses: 3
    Dernier message: 11/02/2003, 07h22
  4. Ordre de parcours de l'arbre...
    Par Sylvain James dans le forum XML/XSL et SOAP
    Réponses: 3
    Dernier message: 01/12/2002, 19h41
  5. [] Tri d'un tableau par ordre alphabétique
    Par cafeine dans le forum VB 6 et antérieur
    Réponses: 3
    Dernier message: 17/09/2002, 09h43

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