Die Zeit Komplexität des Zählens Sortierung

Question

Ich nehme einen Algorithmus Kurs und da sah ich, dass die Zeit Komplexität des Zählens Sort ist O (n + k) wo k ist der Bereich der Zahlen und n ist die Eingangsgröße. Meine Frage ist, wenn der Unterschied zwischen k und n zu groß ist, wie zum Beispiel wenn k = O (n) oder O (n), können wir sagen, dass die Komplexität ist O (n) oder O (n)? Dann ist das Zählen der Sortierung kein kluger Ansatz, und wir können Merge Sort verwenden. Habe ich recht?

Answer 1

Ja, Sie sind in jeder Hinsicht genau richtig.

Darüber hinaus können wir stärker Aussagen machen: wenn k = O (n) oder O (n), können wir sagen, dass die Komplexität des Countingsort ist Θ (n) oder Θ (n).

Answer 2

Sie können theoretisch immer noch in O (n) Zeit sortieren. Wenn der Wertebereich 1 bis 0 ist, dann wandle in Basis n um und mache eine Radix-Sortierung. In der Basis n hat die Zahl 3 Ziffern, also ist Ihre Laufzeit O (3n + 3n) + O (n) für die Basiskonvertierung. Gesamt O (n).