0 Daumen
531 Aufrufe

Sortieren durch Verteilen erreicht eine bessere Laufzeitkomplexität als Sortieren durch Vergleichen. Wie erreicht ein Algorithmus, der verteilt, diese Verbesserung der Laufzeit und womit bezahlt er diese Verbesserung?

Avatar von

1 Antwort

0 Daumen

Ein Algorithmus, der verteilt, erreicht die Verbesserung der Laufzeit dadurch, das er den ungefähren Ort des einzusortierenden Elementes durch eine einmalige Berechnung ermittelt, anstatt ihn durch mehrere Vergleiche zu ermitteln.

Die Verbesserung wird dadurch bezahlt, dass die Länge des Schlüssels begrenzt ist.

Avatar von 5,7 k

Ein anderes Problem?

Stell deine Frage