Ximoon (./41) :
Et maintenant, c'est pire ou mieux ?

Mieux. On a le Completely Fair Scheduler d'Ingo Molnár de Red Hat, qui a une complexité proche de O(1) (O(log(N)) dans le pire des cas, O(1) amortisé; en titre de comparaison: le scheduler antique qui avait été remplacé par celui en O(1) était en O(N)!) et produit des résultats nettement meilleurs que le vieux O(1) Scheduler (du même auteur). C'est le fait de garantir ces propriétés qui necessite un arbre binaire balancé (bicolore) et donc une complexité logarithmique dans le pire des cas.