# La complexité

La complexité répond à une question précise : **si mes données deviennent dix fois plus grosses, mon code devient combien de fois plus lent ?**

## Le problème

Le jeu est fluide sur la carte par défaut, 127 cases. Sur la plus grande, 2 611 cases, il ralentit. Le code est pourtant le même. L'auteur a noté à plusieurs endroits « pas très optimisé », sans savoir par où commencer.

La complexité donne une méthode pour repérer **où** ça coince, sans rien mesurer, juste en lisant le code.

## L'idée

On ne compte pas des secondes, qui dépendent de la machine. On compte **combien d'opérations** fait le code en fonction de la taille des données, notée `n`.

Ici, `n` est le nombre de cases de la carte.

## Les cas courants

| Notation | Nom | Si n est multiplié par 10 | Exemple |
| --- | --- | --- | --- |
| O(1) | Constant | Le temps ne change pas | Lire `tiles_by_coo[(3, 4)]` |
| O(log n) | Logarithmique | Le temps augmente à peine | Retirer le plus petit élément d'un tas |
| O(n) | Linéaire | 10 fois plus long | Parcourir toutes les cases |
| O(n log n) | Quasi linéaire | Un peu plus de 10 fois | Trier une liste |
| O(n²) | Quadratique | 100 fois plus long | Pour chaque case, parcourir toutes les cases |

La notation se lit « grand O de n ». Elle garde l'ordre de grandeur et ignore les détails : `3n + 5` opérations, c'est O(n).

<Mermaid
  chart={`flowchart LR
    a["O(1)<br/>toujours pareil"] --> b["O(log n)<br/>presque pareil"] --> c["O(n)<br/>proportionnel"] --> d["O(n log n)<br/>un peu plus"] --> e["O(n²)<br/>explose"]`}
/>

En chiffres, pour les deux tailles de carte du jeu :

| Complexité | 127 cases | 2 611 cases | Rapport |
| --- | --- | --- | --- |
| O(1) | 1 | 1 | 1 |
| O(n) | 127 | 2 611 | 21 |
| O(n²) | 16 129 | 6 817 321 | 423 |

Une carte 21 fois plus grande rend un code quadratique 423 fois plus lent. C'est là que le jeu ralentit.

## Lire la complexité dans le code

### Une boucle : O(n)

```python
for tile in self.tiles:
    tile.draw_tile(self.fog_of_war)
```

Une opération par case.

### Deux boucles imbriquées : O(n²)

```python
for a in self.tiles:
    for b in self.tiles:
        ...
```

Pour chaque case, on reparcourt toutes les cases.

### La boucle cachée

Le cas le plus traître. Aucune seconde boucle visible :

```python
for tile in self.game.map.tiles:
    if tile in total_tiles_owned:
        tile.owner = self.id
```

Mais `in` sur une **liste** est une boucle : Python compare avec chaque élément. C'est donc O(n × m), avec m le nombre de cases possédées.

Les boucles cachées courantes :

| Écriture | Sur une liste | Sur un dictionnaire ou un ensemble |
| --- | --- | --- |
| `x in collection` | O(n) | O(1) |
| `collection.index(x)` | O(n) | sans objet |
| `collection.remove(x)` | O(n) | O(1) |
| `collection.pop(0)` | O(n) | sans objet |
| `collection.append(x)` | O(1) | sans objet |

### Une fonction appelée dans une boucle

```python
for tile in regional_tiles:
    for neighbor in self.game.map.return_neighbors_tiles(tile):
        ...
```

`return_neighbors_tiles` parcourt toute la carte : O(n). Appelée dans une boucle, elle coûte O(n) à chaque tour.

## Dans le jeu

| Code | Complexité | À quelle fréquence | Verdict |
| --- | --- | --- | --- |
| `Map.draw_tiles` | O(n), plusieurs passes | 60 fois par seconde | Le principal coût à l'affichage |
| Survol de la souris, test sur chaque case | O(n) | 60 fois par seconde | Évitable : une conversion de coordonnées suffit |
| `Map.return_neighbors_tiles` | O(n) | À chaque déplacement, expansion | Devient O(1) avec un dictionnaire |
| `Map.update_tile_size` | O(n) | À chaque mouvement de caméra | Inévitable tant qu'on recalcule toutes les cases |
| `Player.update_map_tiles_owner` | O(n × m) | À chaque fin de tour | Devient O(n) avec un ensemble |
| `Player.load_units_owned` | O(u × n) | Au chargement | Sans gravité : une seule fois |
| Génération de la carte | Au moins O(n²) | À la création | L'auteur note que le ralentissement vient de là |

## La fréquence compte autant que la complexité

Un code lent exécuté une fois ne gêne personne. Un code moyen exécuté 60 fois par seconde, si.

<Mermaid
  chart={`flowchart TB
    q1{Exécuté à chaque image ?}
    q1 -- oui --> a[À optimiser en priorité]
    q1 -- non --> q2{Exécuté à chaque action du joueur ?}
    q2 -- oui --> b[À surveiller]
    q2 -- non --> c[Au chargement ou à la création :<br/>laisser tranquille]`}
/>

C'est pourquoi `load_units_owned`, pourtant peu efficace, n'est pas un problème, alors que le test de survol, tout simple, en est un.

## Pathfinding : pourquoi la complexité décide

A* interroge les voisins de chaque case qu'il explore. Sur une grande carte, il peut explorer un millier de cases.

| Recherche des voisins | Coût d'un calcul de chemin sur 2 611 cases |
| --- | --- |
| Avec la liste, O(n) | Environ 1 000 × 2 611, soit 2,6 millions de comparaisons |
| Avec le dictionnaire, O(1) | Environ 1 000 × 6, soit 6 000 recherches |

Et le chemin est recalculé à chaque fois que la souris change de case. Ce n'est pas une optimisation de confort : sans le dictionnaire, le pathfinding est inutilisable.

## La méthode pour optimiser

<Stepper>

1. **Mesurer.** Afficher `clock.get_fps()`, ou chronométrer une fonction. Ne pas deviner.

1. **Trouver le point chaud.** Ce qui s'exécute le plus souvent, avec la plus mauvaise complexité.

1. **Changer la structure de données ou l'algorithme.** Pas les détails d'écriture.

1. **Mesurer à nouveau.** Si rien n'a changé, annuler.

</Stepper>

Pour chronométrer :

```python
import time

start = time.perf_counter()
self.map.draw_tiles()
print(f"draw_tiles : {(time.perf_counter() - start) * 1000:.1f} ms")
```

À 60 images par seconde, une image dispose de 16,7 millisecondes au total.

## Ne pas optimiser trop tôt

L'auteur du jeu a écrit une règle sage en bas de `game.py` : rendre le jeu jouable avant de l'optimiser.

- Un code clair et lent se corrige facilement.
- Un code rapide et illisible ne se corrige plus.
- La plupart du code n'a pas besoin d'être rapide.

Les deux seuls cas où il faut y penser dès le début : ce qui tourne **à chaque image**, et le **choix des structures de données**, parce qu'il est pénible à changer ensuite.

## À retenir

- La complexité dit comment le temps grandit avec les données.
- Une boucle : O(n). Deux boucles imbriquées : O(n²).
- `in` sur une liste est une boucle cachée.
- Fréquence × complexité = priorité.
- Mesurer avant et après.

## Exercices

1. Donner la complexité de `Map.find_possible_neighbors`. Comment la rendre O(1) ?
2. Dans `City.expand`, combien de fois `return_neighbors_tiles` est-elle appelée pour une ville de 15 cases sur la plus grande carte ? Combien de comparaisons au total ?
3. Afficher le nombre d'images par seconde dans un coin de l'écran. Comparer une carte de 7 anneaux et une de 30.
4. Chronométrer `generate_map` pour 10, 20 et 30 anneaux. Le temps est-il proportionnel au nombre de cases ?
