Discussion :

[Hayato]

Bonjour,
J'ai une question concercant un algorithme avec une boucle imbriquée dans une autre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
Pour i de 1 à b1 faire
    ...
     Pour j de 1 à b2 faire
         ...
     Finpour
 Finpour

En supposant que b1 et b2 sont des entiers différents et que les corps d'instructions des boucles ne sont constitués que d'instructions élémentaires, peut-on en déduire que la complexité dans le pire des cas est O(b1*b2) et poser n=b1*b2 et conclure que la complexité est en O(n)? Merci pour d'éventuels éclaircissements.

[Jedai]

peut-on en déduire que la complexité dans le pire des cas est O(b1*b2)

Tout à fait.

poser n=b1*b2 et conclure que la complexité est en O(n)?

Je ne vois pas pourquoi tu voudrais faire ça, ça n'a pas de sens sauf contexte particulier... Une complexité se calcule toujours par rapport à la taille de ses paramètres, s'il y a plusieurs paramètres, il est normal que la complexité dépende de plusieurs tailles. Ici par exemple ce que tu fais aurais un sens si b1 et b2 était les deux dimensions d'une matrices, parce qu'on peut effectivement dire que b1*b2 est la taille de la matrice (et encore, dans certains problèmes on ne pourra pas), mais si b1 était la taille du premier paramètre et b2 la taille du deuxième, faire ce que tu fais est déjà plus contestable...
En plus là la formule est simple, mais imagine une formule en O(b1 * b2 * 2^b1), tu vois bien que tu ne peux plus exprimer ta formule en terme de "n" !

--
Jedaï

[Jedai]

Si tu veux pouvoir écrire O(n), j'imagine que c'est parce que pour toi une complexité doit dépendre d'un seul paramètre pour être rangé en classe de complexité, O(n) correspondant à une complexité linéaire... Pour plusieurs paramètres on parle de classe de complexité par rapport à un paramètre souvent : par exemple premier paramètre de taille n1, deuxième de taille n2.
Complexité O(n1 * 2^n2), alors l'algorithme est de complexité linéaire par rapport au premier paramètre, et exponentielle par rapport au second.

--
Jedaï