Klassenfikation randomisierter Algorithmen

Question

Aus Wikipedia über randomisierte Algorithmen

Man muss zwischen unterscheiden Algorithmen die die zufällige Eingabe verwenden, um die erwartete Laufzeit oder den Speicherverbrauch zu verkürzen, enden jedoch immer mit einem korrekten Ergebnis in einer begrenzten Zeit und zu Probabilistische Algorithmen, die je nach zufälliger Eingabe die Chance haben, ein falsches Ergebnis (Monte -Carlo -Algorithmen) zu erzielen oder ein Ergebnis (Las Vegas -Algorithmen) entweder durch Signalisierung eines Fehlers oder keine Beendetheit zu erzeugen.

1. Ich habe mich gefragt, wie die erste Art von "Algorithmen Verwenden Sie die zufällige Eingabe, um die erwartete Laufzeit oder den Speicherverbrauch zu verkürzen, enden Sie jedoch immer mit einem korrekten Ergebnis einer begrenzten Zeit?
2. Welche Unterschiede zwischen IT und Las Vegas -Algorithmen, die möglicherweise kein Ergebnis erzielen?
3. Wenn ich richtig verstehe, sind probabilistische Algorithmen und randomisierte Algorithmen nicht das gleiche Konzept. Probabilistische Algorithmen sind nur eine Art randomisierte Algorithmen, und die andere Art ist, dass diese die zufällige Eingabe verwenden, um die erwartete Laufzeit oder den Speicherverbrauch zu verkürzen, aber immer mit einem korrekten Ergebnis in einer begrenzten Zeit zu enden?

Answer 1

1. Ein Beispiel für einen solchen Algorithmus wird randomisiert, bei dem Sie die Liste zufällig durchdringen oder den Pivot -Wert zufällig auswählen und dann die schnelle Sortierung wie gewohnt verwenden. Quick Sort hat eine schlechteste Laufzeit von $ o (n^{2}) $, aber auf einer zufälligen Liste hat eine erwartete Laufzeit von $ o (N log n) $, sodass es immer nach $ O (n) endet ^{2}) $ Schritte, aber wir können erwarten, dass die randomisierte Instanz nach $ o (n log n) $ Schritte, immer mit einer korrekten Antwort, endet.

2. Dies ergibt eine Untergruppe von Las Vegas -Algorithmen. Las Vegas -Algorithmen ermöglichen auch die Möglichkeit, dass (mit geringer Wahrscheinlichkeit) möglicherweise überhaupt nicht endet - nicht nur mit etwas mehr Zeit endet.

3. Diese wiederum sind wirklich nur eine Art von Monte -Carlo -Algorithmus, bei dem die Antwort falsch sein kann (mit geringer Wahrscheinlichkeit), was zumindest konzeptionell anders ist als nicht zu antworten.

Es gibt eine ganze Reihe von Details, die ich ausgelassen habe, natürlich möchten Sie vielleicht die Komplexitätsklassen ZPP, RP und BPP nachschlagen, die diese Ideen formalisieren.

Answer 2

Die beiden Begriffe Randomisierte Algorithmen und Probabilistische Algorithmen werden in zwei verschiedenen Kontexten verwendet. Randomisierte Algorithmen sind Algorithmen, die Zufälligkeit verwenden, im Gegensatz zu Gegenständen mit deterministische Algorithmen das nicht. Probabilistische Algorithmen, Zum Beispiel probabilistische Algorithmen für Primalitätstests sind Algorithmen, die Zufälligkeit verwenden und mit einigen (hoffentlich) geringen Wahrscheinlichkeit einen Fehler machen könnten.

Eine wichtige Unterscheidung muss zwischenmacht werden Monte Carlo -Algorithmen und Las Vegas -Algorithmen. Las Vegas -Algorithmen sind randomisierte Algorithmen, die immer die richtige Antwort zurückgeben, aber ihre Laufzeit hängt von den Münzen ab. Ein Beispiel ist Integer Factoring -Algorithmen - sie geben immer die richtigen Faktoren zurück, aber ihre Laufzeit hängt von der Zufälligkeit ab. Bei der Angabe der Laufzeit eines Las Vegas -Algorithmus (sagen wir einen Factoring -Algorithmus), geben wir das tatsächlich an erwartet Laufzeit; Wenn wir Pech haben, könnte der Algorithmus länger laufen.

Monte -Carlo -Algorithmen hingegen sind randomisierte Algorithmus, deren Laufzeit im Voraus festgelegt ist. Solche Algorithmen können einen Fehler machen, aber normalerweise ist die Fehlerwahrscheinlichkeit sehr gering. Ein gutes Beispiel ist die probabilistische Primalitätstests. Diese Algorithmen sind sehr schnell, können jedoch einen Fehler machen. Die Fehlerwahrscheinlichkeit ist jedoch langsam, dass sie in der Praxis niemals einen Fehler machen.

Jeder Las Vegas -Algorithmus kann durch die Ausführung nach lang genug Zeit in einen Monte -Carlo -Algorithmus umgewandelt werden, sodass Las Vegas -Algorithmen in gewissem Sinne "besser" als Monte -Carlo -Algorithmen sind.