Parcours adresse ip et compléxite de programme

**SteelBox** · 07/10/2004, 13h33

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

**Nemerle** · 07/10/2004, 13h48

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....

**SteelBox** · 07/10/2004, 22h25

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 ?

**Médiat** · 07/10/2004, 23h25

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...