Deterministischer vs determinierter Algorithmus?
Hey Leute,
wie schon in der Überschrift erkennbar, verstehe ich diese zwei Arten von Algorithmen nicht ganz? Besonders was der Unterschied sein soll?
Vielen Dank,
Lyn
1 Antwort
Ist ein randomisierter Quicksort determiniert? deterministisch?
Deterministisch keinesfalls, da er das Pivot zufällig auswählt.
Determiniert? QS ist nicht stabil, wenn wir also von einer Unterscheidbarkeit identischer Elemente ausgehen, dann ist er auch nicht determiniert. Sonst ist er determiniert, da er für jede Permutation der gleichen Eingabemenge die gleiche Ausgabe erzeugt, bzw. eben nicht unterscheidbare Permutationen.
----
Man könnte es so sagen: Determiniertheit bezieht sich auf das gleiche Resultat bei gleicher Eingabe, während Determinismus die gleiche Folge innerer Zustände fordert, weswegen deterministische Algorithmen immer auch determiniert sind.