Wie kann die Komplexität von Bucket Sort O(n+k) sein?

Question

Bevor Sie sagen "das wurde schon einmal gefragt" oder "finden Sie ein Algorithmusbuch", lesen Sie bitte weiter und sagen Sie mir, welcher Teil meiner Argumentation falsch war.

Angenommen, Sie haben n Interger und teilen diese in k Bins auf, dann dauert dies O(n) Zeit. Allerdings muss man jeden der k Bins sortieren. Wenn man Quick Sort für jeden Bin verwendet, ist das eine O((n/k) log(n/k))-Operation, so dass dieser Schritt O(n log(n/k)+k). Schließlich muss man dieses Array zusammensetzen, was O(n+k) dauert (siehe diese Stelle ), so dass die gesamte Operation O(n+n log(n/k)+k). Wie wurde nun dieses n log(n/k) verschwunden ist, konnte ich überhaupt nicht herausfinden. Ich vermute, dass es irgendeine Mathematik gibt, die dieses n*log(n/k) eliminiert. Kann mir jemand helfen?

Answer 1

Ihre Vermutung:

• k - die Anzahl der Eimer - ist willkürlich

ist falsch.

Es gibt zwei Varianten der Eimersorte, so dass es ziemlich verwirrend ist.

---

A

Die Anzahl der Eimer ist gleich der Anzahl der Elemente in der Eingabe

Siehe Analyse aquí

---

B

Die Anzahl der Eimer ist gleich R - die Anzahl der möglichen Werte für die eingegebenen ganzen Zahlen

Siehe Analyse aquí y aquí

Answer 2

Ihr Fehler ist die Annahme, dass Quicksort zum Sortieren der Buckets verwendet wird. Normalerweise ist das nicht der Fall, und so vermeiden Sie die (n / k) log(n / k) Bedingungen.

Answer 3

Ihre Analyse sieht gut aus. Der Begriff "Bucketsort" wird für viele verschiedene Algorithmen verwendet. Je nachdem, welchen Sie betrachtet haben, kann die durchschnittliche Laufzeit O(n + k) sein oder nicht.

Wenn ich raten müsste, hätten Sie sich vielleicht eine typische Variante angesehen, bei der man k sehr groß wählt, so dass n/k eine Konstante ist. In einer anderen beliebten Variante ist sogar k >> n, so dass man stattdessen in k/n Schalen unterteilt.

Wenn Sie den Algorithmus im Detail angeben und die Quelle nennen, die behauptet, dass dies im Durchschnitt O(n + k) ist, kann ich meine Antwort revidieren.