Quelle est la complexité d’exécution d’une boucle while dans un programme ?

Voici un aperçu des scénarios courants et de leurs complexités d'exécution :

1. Temps constant (O(1))

* Lorsque la boucle s'exécute un petit nombre de fois fixe, quelle que soit la taille d'entrée. Ceci est rare, mais cela peut se produire si la condition de boucle dépend d'une valeur constante et n'est pas affectée par l'entrée.

```python

je =0

while i <5 :# Boucle exactement 5 fois

imprimer(je)

je +=1

```

2. Temps logarithmique (O(log n))

* Lorsque la boucle réduit la taille du problème d'un facteur constant à chaque itération. Un exemple classique est la recherche binaire.

```python

faible =0

élevé =n - 1

while low <=high :# La boucle continue tant que l'espace de recherche existe

milieu =(bas + haut) // 2

si arr[mid] bas =milieu + 1

elif arr[milieu]> cible :

élevé =moyen - 1

autre:

revenir au milieu # Cible trouvée !

```

Ici, la taille de l'espace de recherche (de « faible » à « élevée ») est environ réduite de moitié à chaque itération. Par conséquent, la boucle s'exécute environ « log2(n) fois.

3. Temps linéaire (O(n))

* Lorsque la boucle parcourt chaque élément d'une entrée de taille `n` une fois. C'est très courant.

```python

je =0

while i print(arr[i]) # Accéder à chaque élément de 'arr' une fois.

je +=1

```

Dans ce cas, le corps de la boucle exécute « n » fois.

4. Temps quadratique (O(n^2))

* Lorsque la boucle itère `n` fois pour chacun des `n` éléments (boucles souvent imbriquées).

```python

je =0

tandis que je j =0

while j imprimer (i, j)

j +=1

je +=1

```

Cela implique une boucle « while » imbriquée, où les deux boucles itèrent « n » fois. Le nombre total d'itérations est « n * n =n^2 ».

5. Autre temps polynomial (O(n^k))

* Généralisations de l'exemple quadratique ci-dessus. Par exemple, trois boucles imbriquées qui itèrent chacune « n » fois entraîneraient une complexité O(n^3).

6. Temps exponentiel (O(2^n)) ou pire

* Le temps d'exécution de la boucle augmente de façon exponentielle avec la taille de l'entrée. Cela indique souvent un algorithme mal conçu ou un problème intrinsèquement très difficile. Les exemples peuvent impliquer d’essayer toutes les combinaisons possibles d’éléments.

Considérations clés :

* Taille d'entrée (n) : Que représente « n » ? La taille d'un tableau, la grandeur d'un nombre, etc. Ceci est essentiel pour exprimer la complexité en termes d'entrée.

* Modifications des variables de condition : Comment la ou les variables contrôlant la condition de la boucle changent-elles au sein de la boucle ? Augmente-t-il d’un montant constant, diminue-t-il d’un facteur, etc. ?

* Opérations à l'intérieur de la boucle : Le temps d'exécution des opérations *à l'intérieur* de la boucle est important. Si, par exemple, vous avez une opération O(n) dans une boucle qui s'exécute n fois, la complexité globale est O(n * n) =O(n^2).

Comment déterminer la complexité d'exécution :

1. Identifiez la taille d'entrée (n) : Quel est le paramètre de taille pertinent ?

2. Déterminez le nombre d'itérations : Combien de fois la boucle s'exécute *par rapport à `n`* ? C’est la partie centrale.

3. Considérez les opérations à l'intérieur de la boucle : Si la boucle contient des opérations complexes, leur complexité d'exécution doit être prise en compte. La complexité globale devient la complexité des itérations de la boucle multipliée par la complexité de l'opération la plus coûteuse au sein de la boucle.

4. Exprimer la complexité : Utilisez la notation Big O (O( ), Ω( ), Θ( )) pour représenter la limite supérieure, la limite inférieure ou la limite étroite du moteur d'exécution. Généralement, nous nous concentrons sur Big O (dans le pire des cas).

Exemple :

```python

def process_array(arr):

n =len(arr)

je =0

tandis que je j =je + 1

tandis que j si arr[i]> arr[j] :

arr[i], arr[j] =arr[j], arr[i] # Échange de temps constant

j +=1

je +=1

retour arr

```

Analyse :

* `n` est la longueur du tableau d'entrée `arr`.

* La boucle externe (`i`) s'exécute `n` fois.

* La boucle interne (`j`) s'exécute environ `n - i` fois. Dans le pire des cas, lorsque « i » vaut 0, il s'exécute « n » fois.

* L'opération d'échange à l'intérieur de la boucle interne est O(1).

Par conséquent, les boucles imbriquées contribuent à la complexité O(n^2). L'échange est à temps constant et n'affecte pas le temps d'exécution global de O(n^2). Cet algorithme est similaire au tri par sélection.

En résumé, pour déterminer la complexité d'exécution d'une boucle « while », analysez soigneusement le nombre de fois que la boucle s'exécute par rapport à la taille d'entrée et tenez compte de la complexité des opérations effectuées dans la boucle.