Point de départ: deux programmes d'une complexité exponentielle en théorie.
 
On verra que la pratique est différente: un est exponentiel alors que l'autre est
de facto linéaire. Une vidéo qui montre cela est disponible à
www.youtube.com/watch?v=9NE0rdLM3Zg J'ai déjà présenté ces programmes l'an dernier
dans le cadre de la même session. Je renvoie le lecteur vers ma communication de
2022 pour des explications techniques.


Beaucoup ont pu penser à l'époque que c'était un cas isolé lié à une configuration
ou à une installation atypique de mon Linux. Or j'ai depuis vérifié ce
comportement avec mes collègues de laboratoire ou via un sondage public sur la
liste du gdrro (le 21/11/22). Environ 50 personnes m'ont répondu pour confirmer
sur leurs machines le constat de linéarité sus-cité. Ce constat a été infirmé
(peut-être!) par une seule personne X, qui n'a pas réagi à ma relance pour
m'assurer qu'il ne s'agit pas d'une erreur de copier coller dans son mail. Une
chose est claire: s'il y une machine avec une configuration atypique, ce n'est pas
une des 50 machines ci-dessus, mais celle de X.

Lors de mon sondage sur la liste du gdrro, plusieurs personnes ont commencé à
donner des éléments sur calloc et malloc pour expliquer le manque de corrélation
entre le temps de calcul théorique et le temps de calcul réel. Mais ce qui devait
arriver est arrivé: quelqu'un a rebondit pour exprimer ses doutes que cela soit
vraiment un sujet de recherche qui mérite d'être débattu sur la liste. La
discussion a été arrêtée. Cela rejoint la question du titre et on va essayer de
donner des pistes pour s'y extraire.