Was ist die zeitliche Komplexität der Schlafsorte?

Wie drücken Sie angesichts dieses Sortieralgorithmus seine zeitliche Komplexität aus?

Ursprünglich hier vorgestellt (Teilarchiv) .

#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

example usage:
./sleepsort.bash 5 3 6 3 6 3 1 4 7

O(max(input)+n)

Die Komplexität scheint nur umständlich auszudrücken, da die meisten Sortieralgorithmen datenunabhängig sind. Ihre Zeit skaliert mit der Datenmenge, nicht mit den Daten selbst.

FWIW, wie hier ausgeführt , ist dies kein zuverlässiger Algorithmus zum Sortieren von Daten.

Ein Punkt, den anscheinend niemand angesprochen hat, ist die Art und Weise, wie diese sleepumgesetzt werden. Letztendlich landen sie irgendwo in einem Scheduler, und die Komplexität des Betriebs hängt vom verwendeten Scheduling-Algorithmus ab. Wenn die sleeps beispielsweise als Ereignisse in eine Prioritätswarteschlange gestellt werden, erhalten Sie wahrscheinlich etwas, das dem Heapsort entspricht, mit der Komplexität O (n log n) . Ein naiver Planungsalgorithmus kann zu O (n ^ 2) führen .

Ich denke, paxdiablo ist am nächsten, aber nicht aus dem richtigen Grund. Die Zeitkomplexität ignoriert Probleme auf realer Hardware wie Cache-Größen, Speicherbeschränkungen und in diesem Fall die begrenzte Anzahl von Prozessen und den Betrieb des Schedulers.

Basierend auf der Wikipedia-Seite für Zeitkomplexität würde ich sagen, dass die Antwort lautet, dass Sie die Laufzeitkomplexität nicht bestimmen können, denn wenn sie definiert ist als:

Die Zeitkomplexität wird üblicherweise durch Zählen der Anzahl der vom Algorithmus ausgeführten Elementaroperationen geschätzt, wobei die Ausführung einer Elementaroperation eine feste Zeitdauer benötigt. Somit unterscheiden sich die benötigte Zeit und die Anzahl der vom Algorithmus ausgeführten Elementaroperationen um höchstens einen konstanten Faktor.

Dann können wir nicht über die Laufzeitkomplexität dieses Algorithmus sprechen, da die Zeit, die die Elementaroperationen benötigen, so stark unterschiedlich ist, dass sich die benötigte Zeit um mehr als einen konstanten Faktor unterscheiden würde.

Sowohl die zeitliche Komplexität als auch die Prozesskomplexität dieses Algorithmus sind O(braindead):

• Mit einem ausreichend großen Wert im Datensatz warten Sie auf eine Antwort, bis die Sonne explodiert (2 ⁶⁴ Sekunden sind etwas mehr als eine halbe Billion Jahre).
• Bei einer ausreichend großen Datensatz Größe, werden Sie (a) treffen Sie Ihr Prozesslimit; und (b) feststellen, dass der frühe Schlaf endet, bevor die letzteren beginnen, was bedeutet, dass das Set (2,9,9,9,9,9,...,9,9,1)das 1und nicht 2korrekt sortiert .

Die zeitliche Komplexität spielt in diesem Fall keine Rolle. Sie können nicht bekommen nicht weniger optimiert als „falsch“. Es ist in Ordnung, eine Komplexitätsanalyse zu verwenden, um Algorithmen zu vergleichen, wenn sich die Größe des Datensatzes ändert, aber nicht, wenn die Algorithmen überhaupt lächerlich sind :-)

Ich bin mit Jordan zusammen, außer dass ich denke, dass die Komplexität der Wanduhrzeit besser als O (2 ^ m) ausgedrückt wird, wobei m die Größe jedes Elements ist, als O (max (Eingabe)).

Wenn jedes Element die Größe m hat, hat das größte Element den ganzzahligen Wert 2 ^ m (minus eins, aber das interessiert niemanden). Konstruktionsbedingt erfordert der Algorithmus, dass die Rüstzeit kleiner als 1 ist, eine Konstante.

Also Wanduhrzeitkomplexität O (2 ^ m), Operationszählkomplexität O (n).

Ein modifizierter Algorithmus, der die Einrichtungszeit berücksichtigt, würde wahrscheinlich die Komplexität der Wanduhrzeit O (2 ^ m + n) aufweisen. Zum Beispiel könnte es die aktuelle Zeit am Anfang notieren, berechnen base_time = start_time + k*len(list)(für eine geeignete Konstante k) und dann die Threads bis zur Zeit schlafen lassen base_time+i. Dann k*len(list)ist eindeutig O (n) und iist O (2 ^ m) wie zuvor für insgesamt O (2 ^ m + n).

Wenn Sie den Thread lesen, werden Sie sehen, dass Ihre Frage bereits beantwortet ist. Die zeitliche Komplexität ist O(max(input))und die betriebliche Komplexität (Anzahl der Operationen) ist O(n).

Obwohl es linear aussieht, denke ich, dass die Komplexität immer noch O ist (log (n) * max (Eingabe)).

Wenn wir über asymptotische Zeitkomplexität sprechen, bedeutet dies, wie viel Zeit benötigt wird, wenn n unendlich groß wird.

Ein vergleichsbasierter Sortieralgorithmus kann nicht schneller als O (n * log (n)) sein, und die Schlafsortierung ist tatsächlich vergleichsbasiert:

Die Prozesse schlafen n Sekunden und wachen auf. Das Betriebssystem muss die am wenigsten verbleibende Schlafzeit aus dem gesamten Schlafprozess ermitteln und diejenige aktivieren, wenn es an der Zeit ist.

Dies erfordert eine Prioritätswarteschlange, die O (logN) Zeit zum Einfügen eines Elements und O (1) zum Finden des minimalen Elements und O (logN) zum Entfernen des minimalen Elements benötigt.

Wenn n sehr groß wird, dauert es mehr als 1 Sekunde, um einen Prozess aufzuwecken, wodurch er größer als O (n) wird.