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é algorithme boucle pour


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau membre du Club
    Femme Profil pro
    Étudiant
    Inscrit en
    mars 2019
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Canada

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2019
    Messages : 39
    Points : 38
    Points
    38
    Par défaut Complexité algorithme boucle pour
    Bonjour,
    Quelqu'un pourrait-il m'aider à trouver la complexité de cet algorithme:
    Pour i de 1 à n
    i=2^i

    Merci

  2. #2
    Membre confirmé
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    138
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 138
    Points : 529
    Points
    529
    Par défaut
    Bonjour,
    tu as essayé de te faire une idée des valeurs successives ?
    tu sais que ce n'est jamais une bonne idée de modifier le variable index d'une boucle dans la boucle …
    connais-tu la notation des exposants itérés de Knuth ? sais-tu ce que représente dans cette notation 2↑↑n ?

  3. #3
    Nouveau membre du Club
    Femme Profil pro
    Étudiant
    Inscrit en
    mars 2019
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Canada

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2019
    Messages : 39
    Points : 38
    Points
    38
    Par défaut
    Citation Envoyé par WhiteCrow Voir le message
    Bonjour,
    tu as essayé de te faire une idée des valeurs successives ?
    tu sais que ce n'est jamais une bonne idée de modifier le variable index d'une boucle dans la boucle …
    connais-tu la notation des exposants itérés de Knuth ? sais-tu ce que représente dans cette notation 2↑↑n ?
    bONJOUR,
    Effectivement j'ai pu voir comment varier les valeurs de i à chaque itération mais je n'arrive pas à trouver une expression générale. Et non malheureusement c'est la première fois que j'en entends parlé

  4. #4
    Membre confirmé
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    138
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 138
    Points : 529
    Points
    529
    Par défaut
    Et avec la puissance itérée ?
    Donc j'imagine que tu n'en connais pas l'inverse : le logarithme itéré (aka log*) ?

    Avec tout ce que tu viens de découvrir, arrives-tu à une solution ?

  5. #5
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 176
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 74
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 176
    Points : 2 280
    Points
    2 280
    Billets dans le blog
    9
    Par défaut Complexité algorithme boucle pour
    Bonjour,

    Citation Envoyé par Fvb02 Voir le message
    Bonjour,
    Quelqu'un pourrait-il m'aider à trouver la complexité de cet algorithme:
    Pour i de 1 à n
    i=2^i
    Ne s'agirait-il pas plutôt de la relation ui+1 = 2^ui ?

    Cela redeviendrait compréhensible.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  6. #6
    Nouveau membre du Club
    Femme Profil pro
    Étudiant
    Inscrit en
    mars 2019
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : Canada

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mars 2019
    Messages : 39
    Points : 38
    Points
    38
    Par défaut
    Peut on alors dire que la complexité est logarithmique?

  7. #7
    Membre confirmé
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    juillet 2020
    Messages
    138
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 48
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : juillet 2020
    Messages : 138
    Points : 529
    Points
    529
    Par défaut
    Non, elle largement sous logarithmique. La complexité temporelle est à vue de nez en O( log* n ) ou similaire. C'est une fonction qui croît hyper lentement bien plus lentement qu'un log puisque c'est la fonction inverse d'une puissance itérée qui croît bien plus rapidement qu'une exponentielle. Par exemple pour le code que tu donnes, il n'y aura pratiquement jamais plus de 3 tours de boucle … ici pratiquement signifie «en pratique avec les plateformes actuelles».

  8. #8
    Membre expérimenté

    Homme Profil pro
    Directeur de projet
    Inscrit en
    mai 2013
    Messages
    425
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Directeur de projet
    Secteur : Service public

    Informations forums :
    Inscription : mai 2013
    Messages : 425
    Points : 1 356
    Points
    1 356
    Par défaut De loin en loin
    Bonjour WhiteCrow,
    Citation Envoyé par WhiteCrow Voir le message
    Non, elle largement sous logarithmique. La complexité temporelle est à vue de nez en O( log* n ) ou similaire. C'est une fonction qui croît hyper lentement bien plus lentement qu'un log puisque c'est la fonction inverse d'une puissance itérée qui croît bien plus rapidement qu'une exponentielle. Par exemple pour le code que tu donnes, il n'y aura pratiquement jamais plus de 3 tours de boucle … ici pratiquement signifie «en pratique avec les plateformes actuelles».
    Oui, mathématiquement par rapport à n.

    Mais un algorithme travaille dans le concret qui n'a pas l'élégance des mathématiques :
    • Comme tu l'as fait remarquer, c'est une très mauvaise idée de modifier l'indice d'une boucle dans la boucle. Premier effet, si n est supérieur à 1 et n'est pas une puissance de 2 (et pas n'importe quelle puissance, voir juste après) aucun espoir d'un arrêt quelconque (sauf si le langage transforme implicitement l'égalité i = n en i >= n)
    • La taille est très rapidement un autre problème ingérable même avec des grands nombres et des exposants, car les exposants devraient également être des grands nombres avec des exposants qui... (ce sont également les valeurs de n "acceptables") i0 = 1, i1 = 2, i3 = 4, i4 = 216, i5 =265536...
    • Le problème devient plus intéressant si on suppose que le langage utilisé fait un modulo 2a sans manifester une mauvaise volonté hautement probable (a caractérisant la longueur du type d'entier non signé utilisé), la boucle reste infinie... mais à 0.

    En résumé, ou il fait très peu de pas et tend alors vers une complexité en O(0) mais pour peu de valeurs, ou il tourne sans fin O(oo)

    Je ne suis pas sûr que ce soit vraiment intéressant. En revanche, je n'ai aucun doute sur l'utilité

    Salut
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

Discussions similaires

  1. Boucle : pour chaque élément d'un ensemble ?
    Par monstroplante dans le forum Langage
    Réponses: 7
    Dernier message: 07/11/2005, 15h45
  2. Quel algorithme utilisé pour faire un arbre hiérarchique
    Par deaven dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 26/01/2005, 21h30
  3. Algorithmes génériques pour affichage de primitives 2D.
    Par Selenite dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 02/01/2005, 20h20
  4. boucle pour insérer des enregistrements
    Par roots_man dans le forum ASP
    Réponses: 7
    Dernier message: 05/10/2004, 09h28
  5. Réponses: 2
    Dernier message: 29/05/2002, 20h43

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