Quelle est la complexité la plus défavorable pour le tri par seau ?

Question

Je viens de lire la page Wikipedia sur Triage des seaux . Dans cet article, ils disent que la complexité dans le pire des cas est O(n²). Mais je pensais que la complexité dans le pire des cas était O(n + k) où k est le nombre de seaux. Voici comment je calcule cette complexité :

1. Ajoutez l'élément au seau. En utilisant une liste chaînée, c'est O(1).
2. Parcourir la liste et mettre les éléments dans le bon seau = O(n)
3. Fusionner les seaux = O(k)
4. O(1) * O(n) + O(k) = O(n + k)

Est-ce que j'ai manqué quelque chose ?

Answer 1

Afin de fusionner les buckets, il faut d'abord les trier. Considérons le pseudo-code donné dans l'article de Wikipedia :

function bucketSort(array, n) is
  buckets ← new array of n empty lists
  for i = 0 to (length(array)-1) do
    insert array[i] into buckets[msbits(array[i], k)]
  for i = 0 to n - 1 do
    nextSort(buckets[i])
  return the concatenation of buckets[0], ..., buckets[n-1]

El nextSort(buckets[i]) trie chacun des seaux individuels. En général, un tri différent est utilisé pour trier les compartiments (par exemple, un tri par insertion), car une fois la taille atteinte, des tris différents et non récursifs offrent souvent de meilleures performances.

Maintenant, considérons le cas où tous les n éléments se retrouvent dans le même godet. Si nous utilisons le tri par insertion pour trier les seaux individuels, cela pourrait conduire à la pire des performances, à savoir O(n^2) . Je pense que la réponse doit dépendre du tri que vous choisissez pour trier les seaux individuels.

Answer 2

Que se passe-t-il si l'algorithme décide que chaque élément appartient au même seau ? Dans ce cas, la liste liée de ce seau doit être parcourue à chaque fois qu'un élément est ajouté. Cela prend 1 étape, puis 2, puis 3, 4, 5... n . Ainsi le temps est la somme de tous les nombres de 1 à n ce qui est (n^2 + n)/2, ce qui est O(n^2).

Bien entendu, il s'agit du "pire cas" (tous les éléments dans un seul seau) - l'algorithme permettant de calculer le seau dans lequel placer un élément est généralement conçu pour éviter ce comportement.

Answer 3

Si vous pouvez garantir que chaque seau représente une valeur unique (éléments équivalents), alors la complexité temporelle la plus défavorable serait O(m+n) comme vous l'avez souligné.

Answer 4

Le tri par seau suppose que l'entrée est tirée d'une distribution uniforme. Cela implique que quelques éléments tombent dans chaque seau. En retour, cela conduit à un temps d'exécution moyen agréable de O(n). En effet, si les n éléments sont insérés dans chaque godet de manière à ce que O(1) éléments tombent dans chaque godet différent (l'insertion nécessite O(1) par élément), alors le tri d'un godet à l'aide du tri par insertion nécessite, en moyenne, O(1) également (ceci est prouvé dans presque tous les manuels sur les algorithmes). Puisque vous devez trier n seaux, la complexité moyenne est O(n).

Maintenant, supposons que l'entrée n'est pas tirée d'une distribution uniforme. Comme l'a déjà souligné @mfrankli, cela peut conduire dans le pire des cas à une situation dans laquelle tous les éléments tombent par exemple tous dans le premier seau. Dans ce cas, le tri par insertion nécessitera dans le pire des cas O(n^2).

Notez que vous pouvez utiliser l'astuce suivante pour maintenir la même complexité moyenne O(n), tout en fournissant une complexité O(n log n) dans le pire des cas. Au lieu d'utiliser le tri par insertion, utilisez simplement un algorithme avec une complexité O(n log n) dans le pire des cas : soit le tri par fusion, soit le tri par tas (mais pas le tri rapide, qui n'atteint O(n log n) qu'en moyenne).

Answer 5

Ceci est une réponse complémentaire à @perreal. J'ai essayé de la poster en tant que commentaire mais elle est trop longue. @perreal indique correctement quand le tri par seau est le plus judicieux. Les différentes réponses font des hypothèses différentes sur les données à trier. Par exemple, si les clés à trier sont des chaînes de caractères, alors la gamme des clés possibles sera trop grande (plus grande que le tableau de seaux), et nous devrons utiliser uniquement le premier caractère de la chaîne pour les positions de seaux ou une autre stratégie. Les seaux individuels devront être triés car ils contiennent des éléments avec des clés différentes, ce qui conduit à O(n^2).

Mais si nous trions des données dont les clés sont des nombres entiers dans un intervalle connu, alors les seaux sont toujours déjà triés parce que les clés dans le seau sont égales, ce qui conduit au tri en temps linéaire. Non seulement les seaux sont triés, mais le tri est aussi plus rapide. stable parce que nous pouvons retirer les éléments du tableau du seau dans l'ordre où ils ont été ajoutés.

La chose que je voulais ajouter est que si vous êtes confrontés à O(n^2) en raison de la nature des clés à trier, le tri par seau pourrait ne pas être la bonne approche. Lorsque vous avez une gamme de clés possibles qui est proportionnelle à la taille de l'entrée, alors vous pouvez profiter du temps linéaire du tri par seau en ayant chaque seau contenant seulement 1 valeur d'une clé.