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

Python Discussion :

Nombre d'instruction et complexité


Sujet :

Python

  1. #1
    Nouveau membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2017
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : Suisse

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2017
    Messages : 6
    Par défaut Nombre d'instruction et complexité
    Bonjour, un exercice me demande d'exprimer les valeurs "total" sous la forme d'une fonction de l'entrée n ainsi que de donner la complexité théorique en fonction du paramètre n avec la notation 0(..) :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    def f1(n): 
        total = 0
        for i in range(0,n):
               total += 1
        for j in range(0,2*n):
               total += 1
        for k in range(0,3*n): 
               total += 1
        return total
    Je trouve 6n avec une complexité de 0(n) c'est bien juste ?

    deuxième exemple :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    def f4(n):
           total =0
           i=1
           while i<n:
                 i *=2
                 total += 1
           return total
    Je trouve la complexité 0(log2(n)) mais je ne parviens pas à exprimer le nombre d'instruction ...

    Merci de votre aide !

  2. #2
    Nouveau candidat au Club
    Homme Profil pro
    Université de Fribourg
    Inscrit en
    Octobre 2017
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Suisse

    Informations professionnelles :
    Activité : Université de Fribourg

    Informations forums :
    Inscription : Octobre 2017
    Messages : 2
    Par défaut
    Salut, pour le dernier (f4(n)) la complexité est : O(ln(n)) et la valeur retournée total est : ln(n) / ln(2)
    excuse moi, question peut-être indiscrète mais tu étudies dans quelle université ?

  3. #3
    Nouveau membre du Club
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2017
    Messages
    6
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : Suisse

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2017
    Messages : 6
    Par défaut
    merci pour la réponse ! pourquoi il y a cette division par ln(2) ?
    Je suis à l'université de Fribourg comme vous

  4. #4
    Nouveau candidat au Club
    Homme Profil pro
    Université de Fribourg
    Inscrit en
    Octobre 2017
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Suisse

    Informations professionnelles :
    Activité : Université de Fribourg

    Informations forums :
    Inscription : Octobre 2017
    Messages : 2
    Par défaut
    ah hahahaha
    euh car tu sais qu'on prend tous les n strictement plus petit que n, mais dans la boucle while, il y'a une deuxième condition.
    Cette condition c'est le fait de multiplier i par 2, donc en gros ça va faire ( 1*2, ensuite 2*2, ensuite 4*2, ensuite 8*2...) donc imagine n c'est 20, bah en entrant dans la boucle while, i fera 8, ensuite ça fera 8*2, et ce sera strictement inférieur, si tu refais fois 2 on est déjà à 32
    tout cela c'est pour te montrer que c'est pas i qui doit être plus petit que n (i <n) mais c'est plutôt i*2 qui doit être plus petit que n (i*2 < n)
    Donc pour déterminer le nombre i pour que i*2 reste toujours plus petit que n, j'ai résolu l’équation 2^i = n ce qui fait ln(2*i) = ln(n), ce qui fait encore x(ln(2)) < ln(n), et finalement x < ln(x) / ln(2)
    donc sur la ligne de la boucle While et pour les deux lignes à l'intérieur de la boucle, le nombre d’instructions est de "ln(x) / ln(2)" chacune.
    j'ai beaucoup parlé mais j'espère que t'as capté

Discussions similaires

  1. Réponses: 8
    Dernier message: 27/08/2015, 10h49
  2. [Microcontrôleur] Évaluer un bout de code en nombre d'instructions
    Par Tiberizz dans le forum Autres architectures
    Réponses: 2
    Dernier message: 06/10/2010, 05h16
  3. [AC-2007] NOMBRE ENTIER instruction INT(x)
    Par JPJOLY dans le forum IHM
    Réponses: 0
    Dernier message: 16/03/2010, 18h44
  4. Complexité en terme de nombre de flops
    Par shinobida dans le forum Algorithmes et structures de données
    Réponses: 15
    Dernier message: 25/04/2008, 15h20

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