0
Si l'on suppose que les éléments sont uniformément répartis dans une plage donnée k, nous avons 10 godets. Ensuite, la quantité d'éléments dans chaque compartiment sera la même après une itération sur les n éléments de la liste. Ensuite, par exemple, nous utilisons quicksort pour trier chacun des buckets, mais nous savons que le nombre d'éléments dans chaque bucket est constant, donc le temps de fonctionnement total ne sera-t-il pas Θ (n)?Temps de fonctionnement du tri par godet
Est-ce que ce sont les devoirs? Quelles sont vos idées pour aborder la question? – reto
@reto Non, je me prépare pour un examen en introduction aux algorithmes, et beaucoup de sources donnent des informations différentes concernant la durée de fonctionnement. – Petter
Si vous avez 10 buckets et n éléments, le nombre d'éléments dans chaque bucket est n/10, ce qui n'est pas une constante. – whrow