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 :

Parcours adresse ip et compléxite de programme


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éclairé Avatar de SteelBox
    Profil pro
    Inscrit en
    Novembre 2002
    Messages
    446
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations forums :
    Inscription : Novembre 2002
    Messages : 446
    Par défaut Parcours adresse ip et compléxite de programme
    Bonjour,
    En fait, j'ai un programme ou l'utilisateur saisi 2 adresses ip valides; c'est à dire comprises entre 000.000.000.000 et 255.255.255.255.
    J'aimerais savoir quelle est la meilleure manière pour parcourir les adresses depuis la première jusqu'à la deuxième ?

    L'idée de faire 4 boucles imbriquées me semble correct mais peut être un peu long car il s'agit d'un algorithme de compléxité n^4.
    Faire une seule boucle me semble possible (soit un algo de compléxité n)
    Par contre, je ne suis pas sûr que la différence soit flagrante entre les 2 algos malgré la différence de compléxité.
    Quelqu'un peut il m'éclairer la dessus et me dire qu'elle serait le meilleur algo possible ?

    Merci

  2. #2
    Membre Expert Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 55

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Par défaut
    La complexité n'est pas affaire de boucles imbriquées!
    Exemple: quelle différence entre
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    n=p*p;
    for(int i=1;i<n;i++)
    et
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    for(int i=1;i<n;i++){
       for(int j=1;j<n;j++){
    Donc tes quatres boucles imbriquées me semblent parfaites!
    Passer de 0.0 à 255.255 (je simplifie à 2), va quand même t'obliger à compter 256*256 fois !!

    Si tu préferes une unique boucle, ton calcul reviendra de toute façon au même....

  3. #3
    Membre éclairé Avatar de SteelBox
    Profil pro
    Inscrit en
    Novembre 2002
    Messages
    446
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations forums :
    Inscription : Novembre 2002
    Messages : 446
    Par défaut
    La complexité n'est pas affaire de boucles imbriquées!
    C'est bien ce que je pensais...Donc quand on dit qu'on à un algo en n² ou n^3, ca ne veut rien dire en fait puisque dans mon cas, il y le même nombre d'itération, tout dépend de la valeur de n ?

    Dans mon cas, 4 boucles imbriquées, ca vous semble correct ?

  4. #4
    Inactif   Avatar de Médiat
    Inscrit en
    Décembre 2003
    Messages
    1 946
    Détails du profil
    Informations forums :
    Inscription : Décembre 2003
    Messages : 1 946
    Par défaut
    Citation Envoyé par SteelBox
    C'est bien ce que je pensais...Donc quand on dit qu'on à un algo en n² ou n^3, ca ne veut rien dire en fait puisque dans mon cas, il y le même nombre d'itération, tout dépend de la valeur de n ?
    Bien sur que n² ou n^3 veulent dire quelque chose, c'est simplement la définition de n qui doit être précise, ici le nombre total d'adresse IP est fixe, ce qui peut varier c'est le nombre d'adresse IP entre 2 bornes, tu vas parcourir toutes tes adresses que ce soit avec une boucle ou avec 4 boucles peut importe, au résultat (cf. ce que dit Nemerle) tu auras parcouru les n adresses IP qui existent en n tours de boucles (dont le nombre d'instructions à exécuter est constant, tu ne parles pas d'opérations à effectuer sur les résultats) donc complexité linéaire borné par 256*256*256*256, une adresse IP n'est jamais qu'un nombre de 4 chiffres en base 256.
    Pour te donner une approche de la complexité, demande toi ce qui se passe si tu doubles le nombre d'adresses IP à parcourir, est-ce que ton nombre d'instructions à exécuter est aussi doublé (liénaire), multiplié par 4 (n²), par 8 (n^3) etc...

  5. #5
    Membre éclairé Avatar de SteelBox
    Profil pro
    Inscrit en
    Novembre 2002
    Messages
    446
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations forums :
    Inscription : Novembre 2002
    Messages : 446
    Par défaut
    Ok, j'ai bien compris comment ca marchait. J'ai lu quelques articles sur internet en plus...
    Merci

  6. #6
    Membre Expert Avatar de Nemerle
    Inscrit en
    Octobre 2003
    Messages
    1 106
    Détails du profil
    Informations personnelles :
    Âge : 55

    Informations forums :
    Inscription : Octobre 2003
    Messages : 1 106
    Par défaut
    Et bien use d'un petit [résolu] alors

    Et merci à philippe pour le complément d'info...

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. programme pour trouver l'adresse du port d'un élément
    Par nanou1983 dans le forum Windows Forms
    Réponses: 28
    Dernier message: 20/09/2007, 08h32
  2. Réponses: 2
    Dernier message: 19/08/2007, 11h58
  3. Réponses: 11
    Dernier message: 26/04/2007, 16h34
  4. [WD10] Changer l'adresse IP d'une base HF par programmation
    Par routmout dans le forum WinDev
    Réponses: 1
    Dernier message: 20/06/2006, 20h01
  5. Programme C++ parcours arbo
    Par blooder dans le forum C++
    Réponses: 1
    Dernier message: 26/04/2006, 19h38

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