La mémoire annoncée n'est pas celle qu'on obtient

Elles ne le sont pas, et c'est le point de l'exercice.

Le tableau à deux dimensions occupe $\text{N\_MAX}\times (\text{DEG\_MAX}+1)$ cases, quel que soit le nombre d'arcs. Sa mémoire est donc en $\Theta (n\cdot d_{\max })$, et non en $\Theta (n+m)$ : c'est la mémoire d'un graphe où tous les sommets auraient le degré maximal. Les deux quantités ne coïncident que si les degrés sont à peu près égaux ; dès qu'ils sont inégaux — et ils le sont toujours —, la seconde est plus grande.

Le chiffre. Mesuré pour $n=10^7$, $m=2\cdot 10^7$, avec $4$ octets par entier :

Un facteur $17$ par rapport aux listes véritables — et il grandit proportionnellement à la marge de sécurité DEG_MAX qu'on se donne, puisque la place occupée ne dépend pas du tout de $m$. Sur le réseau social mondial, où le degré moyen est $333$ et le degré maximal des millions, le tableau rectangulaire est hors de question.

Ce que ce tableau reste, et pourquoi le programme le recommande. Ce n'est pas une erreur du cours : c'est un compromis d'épreuve écrite, et le programme le dit ainsi. Il offre trois qualités qui comptent plus que la mémoire quand $n\le 1000$ : aucun malloc, aucun free, aucun pointeur ; un accès direct voisins[u][k] ; et une écriture tenant en trois lignes. Sur les tailles d'un sujet de concours, $2,04$ Go deviennent $20$ kilooctets.

La formulation juste serait donc : « listes d'adjacence : $\Theta (n+m)$ ; leur réalisation par tableau rectangulaire : $\Theta (n\cdot d_{\max })$, à n'employer que si $d_{\max }$ est petit et connu ». La représentation qui atteint véritablement $\Theta (n+m)$ sans allocation dynamique existe, et c'est le tableau de départs du deuxième problème ci-après.

La leçon. Une complexité en mémoire s'énonce pour une structure abstraite ; elle se paye pour une réalisation. Entre les deux, il y a un choix de représentation, et il peut coûter un facteur dix. Le même écart existe pour le temps : un accès annoncé $O(1)$ peut coûter un défaut de cache, comme le montrait le problème sur les deux tris du chapitre chap:tas.