Il m'est arrivé de lire sur Wikipedia que le temps amorti par opération sur un ensemble disjoint (union deux éléments, trouver le parent d'un élément spécifique) est O (a (n)), où a (n) est la fonction inverse d'Ackermann, qui se développe très rapidement.Temps amorti par opération en utilisant des ensembles disjoints
Quelqu'un peut-il expliquer pourquoi cela est vrai?
Eh bien, la page Wikipedia a une citation. Si vous êtes intéressé, vérifiez-le. Si vous êtes à l'université, cela devrait être facile, sinon, trouvez simplement un collège à proximité et utilisez leur bibliothèque (ils s'en fichent si vous n'êtes pas étudiant).
Eh bien, ce serait plutôt difficile à expliquer, parce que ce n'est pas vrai. C'est la fonction d'Ackermann non-inverse qui se développe comme une fusée sur les stéroïdes, l'inverse Ackermann se développe très lentement.
This vous donne le contexte théorique.
Il existe une preuve du fait dans Introduction to Algorithms. C'est une lecture assez populaire, et votre bibliothèque municipale ou scolaire pourrait en avoir une copie. J'ai également vu des copies circuler sur Internet, mais la légalité de celles-ci est probablement discutable.
EDIT: un chunk of the proof semble être lisible sur Google Livres.