Les deux naïves, chiffrées

1. Chaque unir balaye le tableau entier, soit $1000$ lectures ; il y en a $999$. Le total mesuré est de 999 000 lectures — c'est-à-dire, à un facteur près, $n^2$. Sur $n=10^6$ le procédé serait injouable.

2. La seconde naïve écrit p.(trouver p x) <- trouver p y. Déroulons : unir(0,1) donne $p[0]=1$ ; unir(1,2) donne $p[1]=2$ ; et ainsi de suite, $p[k]=k+1$. La forêt est un peigne de profondeur $n-1$, enraciné en $n-1$. Sur $n=20000$, la profondeur mesurée est bien de $19999$, et trouver(0) coûte autant de remontées.

Le point commun aux deux : chacune est optimale pour une opération et catastrophique pour l'autre. La suite d'unions ci-dessus est le pire cas des deux à la fois, ce qui est instructif : elle n'a rien d'exotique — c'est simplement l'ordre naturel dans lequel on lit une liste d'arêtes.