Was ist der Unterschied zwischen deterministischen und nichtdeterministischen Algorithmen?


Antwort 1:

Ich gehe davon aus, dass die Frage von einem Studenten der Comp Sci im ersten Jahr gestellt wird. Also werde ich antworten, um ihre Verwirrung zu beseitigen, ohne zu viel wissenschaftlichen Jargon zu verwenden.

Ein einfacher Test, um festzustellen, ob ein Algo deterministisch ist oder nicht. Überprüfen Sie einfach, ob der Pseudocode des Algorithmus eine zufällige Komponente enthält.

Wenn Sie einem deterministischen Algorithmus dieselbe Eingabe in derselben Reihenfolge geben, dauert es alternativ dieselbe Zeit, um eine Lösung zu finden und jedes Mal dieselbe exakte Lösung zu finden. Während ein nicht deterministischer Algorithmus etwas mehr / weniger Zeit in Anspruch nehmen kann und möglicherweise nicht jedes Mal eine andere Antwort für dieselbe Eingabe in derselben Reihenfolge gibt.

Beispiel: - Die Sortierung zusammenführen ist ein deterministischer Algorithmus, da jedes Mal, wenn Sie die Eingabe X eingeben, die gleichen Vergleiche in genau derselben Reihenfolge durchgeführt werden und Sie genau dieselbe Antwort erhalten.

Quicksort gibt zwar die richtige Antwort, kann jedoch eine etwas andere Zeit in Anspruch nehmen, um die Antwort auszugeben, da die von der QuickSort-Subroutine durchgeführten Vergleiche in jedem Lauf unterschiedlich sind.


Antwort 2:

Deterministisch bedeutet eine genaue Antwort oder ein genaues Ergebnis. Analog dazu ist der Unterschied zwischen stichprobenbasierten und Standard-Medianfindungsalgorithmen. Dies ist auch bei kombinatorischen Algorithmen wie dem Packen von Behältern der Fall, bei denen bisher keine Heuristik in jedem Fall als die optimalste Lösung erwiesen werden konnte.