C’est ce que j’ai pensé aussi, d’un point de vue algorithmique, si on considère le petit bout de code du lien, c’est le cas.
Mais comme dit au dessus et dans le lien, les propriétés (complexité&co) dépendent de la façon dont tu prépares tes tâches pour les réveiller au moment opportun, à la fin du sleep. Si le système d’exploitation utilise un algorithme de tri pour préparer les processus qui dorment, alors la complexité du sleep sort ne pourra pas être meilleure que la complexité du tri fait par le système :
— c’est un peu couillon vu que le tri comptage est en O(N), je classerais même presque le sleep sort dans la classe O(1), car l’opération de tri ne dépend pas de la taille du tableau (presque car il reste les opérations d’accès mémoire&co) ;
— on ne peut plus parler de tri par comptage car lorsqu’on déroule l’opération sleep un tri apparaîtra, c’est qu’il n’est pas explicite mais bien présent ;
— toute la question est alors de savoir ce qui est implémenté derrière sleep pour vraiment parler d’un tri comptage.
[^] # Re: Tri comptage
Posté par BB . En réponse au journal Une autre excuse pour ne pas bosser.... Évalué à 1.
C’est ce que j’ai pensé aussi, d’un point de vue algorithmique, si on considère le petit bout de code du lien, c’est le cas.
Mais comme dit au dessus et dans le lien, les propriétés (complexité&co) dépendent de la façon dont tu prépares tes tâches pour les réveiller au moment opportun, à la fin du sleep. Si le système d’exploitation utilise un algorithme de tri pour préparer les processus qui dorment, alors la complexité du sleep sort ne pourra pas être meilleure que la complexité du tri fait par le système :
— c’est un peu couillon vu que le tri comptage est en O(N), je classerais même presque le sleep sort dans la classe O(1), car l’opération de tri ne dépend pas de la taille du tableau (presque car il reste les opérations d’accès mémoire&co) ;
— on ne peut plus parler de tri par comptage car lorsqu’on déroule l’opération sleep un tri apparaîtra, c’est qu’il n’est pas explicite mais bien présent ;
— toute la question est alors de savoir ce qui est implémenté derrière sleep pour vraiment parler d’un tri comptage.