Was bedeutet die erwartete Laufzeit und die durchschnittliche Laufzeit eines Algorithmus?

17

Angenommen, wir möchten die Laufzeit von Algorithmen analysieren. Manchmal sagen wir, wir wollen die Laufzeit eines Algorithmus finden, wenn die Eingabegröße n ist, und im schlimmsten Fall wird sie mit O (n) bezeichnet. Manchmal sehe ich Bücher / Papiere, die sagen, dass wir die erwartete Zeit eines Algorithmus finden müssen. Manchmal wird auch die durchschnittliche Laufzeit verwendet.

Was ist "erwartete Zeit"? In welchen Fällen ist es sinnvoll, die erwartete Zeit anstelle der Worst-Case-Zeit zu ermitteln?

Bearbeiten : Ich denke, es gibt einen subtilen Unterschied zwischen der erwarteten Laufzeit und der durchschnittlichen Laufzeit, aber ich bin nicht sicher. Durch diesen Beitrag möchte ich den genauen Unterschied wissen, falls vorhanden.

Aussenseiter
quelle
1
Vermutlich meinen sie den Durchschnittsfall ..
Martijn Pieters
4
Der Erwartungswert einer Wahrscheinlichkeitsverteilungsfunktion wird als Integral von x * f (x) von negativ nach positiv unendlich beschrieben. Die erwartete Zeit wird abgeleitet, indem die Wahrscheinlichkeitsverteilung aller möglichen Zeiten bestimmt und dann der erwartete Wert genommen wird. Diese Operation wird üblicherweise als Mittelwert- oder Durchschnittswertberechnung bezeichnet .
Joel Cornett
1
@ JoelCornett: Das wäre eine gute Antwort, wenn Sie es gepostet ..
Martijn Pieters
@MartijnPieters: Nein, der Durchschnittsfall nimmt die Wahrscheinlichkeitsverteilung der Eingaben an, der erwartete Fall nicht.
Jörg W Mittag
@ JörgWMittag: Richtig, wenn Sie die reale Wahrscheinlichkeitsverteilung Ihrer Eingaben kennen, können Sie den Durchschnittsfall ignorieren. Mit anderen Worten, der erwartete Fall ist die Zeit, die Ihr Algorithmus benötigt, um die Wahrscheinlichkeitsverteilung der erwarteten Eingabesätze zu ermitteln.
Martijn Pieters

Antworten:

15

Die erwartete Zeit ist nur die durchschnittliche erwartete Laufzeit des Algorithmus unter Verwendung der beabsichtigten Eingabe.

Angenommen, Sie haben einige Millionen Benutzerdatensätze und möchten diese sortieren. Möglicherweise möchten Sie einen Algorithmus verwenden, der für Ihre Eingabe am besten geeignet ist und als solcher die erwartete Laufzeit liefert , im Gegensatz zu einem Algorithmus mit besserer Laufzeit Worst-Case-Laufzeit, aber schlechter erwartete Laufzeit.

Manchmal sind zum Beispiel die konstanten Faktoren für die Zeitkomplexität eines Algorithmus so hoch, dass es Sinn macht, Algorithmen mit geringerer Zeitkomplexität, aber kleineren konstanten Faktoren zu verwenden, da Sie eine bessere erwartete Laufzeit mit geringem Input erhalten, obwohl dies der Fall wäre mit größerem Input eine schreckliche Outperformance erzielen.

Ein besseres Beispiel wäre vielleicht der klassische Quicksort-Algorithmus, der ungeachtet der Eingabe eine Laufzeit im ungünstigsten Fall von O (n²), aber eine erwartete durchschnittliche Laufzeit von O (n log n) aufweist . Dies liegt daran , der Algorithmus verwendet (oder besser gesagt, verwenden kann , abhängig von der Implementierung) Randomisierung. Es ist also ein sogenannter randomisierter Algorithmus . Es läuft bei jedem Aufruf etwas anders, auch bei gleicher Eingabe. Daher gibt es für die Implementierung keine universelle Worst-Case-Eingabe, da die Worst-Case-Eingabe davon abhängt, wie der Algorithmus den Drehpunkt zum Teilen der gegebenen Eingabe auswählt. Aus diesem Grund kann man nicht einfach einen vordefinierten Eingang bereitstellen, der die Laufzeit im ungünstigsten Fall verursacht. Dies ist häufig bei randomisierten Algorithmen der Fall, die unabhängig von der Eingabe eine besser erwartete durchschnittliche Laufzeit anstreben.

Es geht darum, den richtigen Algorithmus für die Eingabe zu verwenden.

zxcdw
quelle
Hervorragende Antwort. Vielen Dank . Ich denke, der Unterschied zwischen erwartet und durchschnittlich ist, dass wenn wir die Verteilung der Eingaben kennen und den Algorithmus ausführen, dies als "Durchschnitt" bezeichnet wird und wenn wir einen Zufallszahlengenerator verwenden, um die vorliegenden Eingaben zu permutieren, dies als erwartete Laufzeit bezeichnet wird. Stimmen Sie dieser Prämisse zu?
Geek
4

Die erwartete Laufzeit eines randomisierten Algorithmus ist genau wie die Laufzeit im ungünstigsten Fall ein genau definiertes Konzept. Wenn ein Algorithmus randomisiert ist, ist seine Laufzeit ebenfalls zufällig, was bedeutet, dass wir den erwarteten Wert seiner Laufzeit definieren können.

Ein bekanntes Beispiel ist Quicksort: Wenn wir die Pivots zufällig auswählen, können wir nachweisen, dass die erwartete Laufzeit O (n log n) ist, obwohl die Laufzeit im ungünstigsten Fall O (n ^ 2) bleibt. Ein Beispiel, bei dem die Randomisierung sehr mächtig ist, ist das kleinste Einschlusskreisproblem: Es gibt einen einfachen Algorithmus, dessen Laufzeit im ungünstigsten Fall O (n ^ 3) ist, dessen Laufzeit jedoch erwartungsgemäß nur O (n) ist.

Die durchschnittliche Laufzeit wird normalerweise verwendet, wenn über das Verhalten eines Algorithmus 'für die meisten Eingaben' gesprochen wird. Wir definieren eine Art der zufälligen Erzeugung einer Eingabe, zum Beispiel füllen wir ein Array mit Zufallszahlen oder wir permutieren die Zahlen 1 bis n zufällig (also keine Duplikate), oder wir werfen eine Münze und erhalten entweder eine absteigende oder eine aufsteigende Menge von zahlen. Die durchschnittliche Laufzeit eines Algorithmus für diese zufällige Verteilung von Eingaben ist dann die erwartete Laufzeit des Algorithmus (in diesem Fall ist der Algorithmus möglicherweise nicht randomisiert, die Eingabe jedoch).

Als Beispiel: Es gibt geometrische Probleme, für die Algorithmen existieren, die auf den ersten Blick gut zu funktionieren scheinen, bis Sie eine sehr seltsame Art der Verteilung beispielsweise der Eingabezeilen entdecken. Wenn Sie annehmen, dass die Zeilen zufällig verteilt sind, kann es sein, dass diese seltsamen Szenarien äußerst unwahrscheinlich sind, sodass Ihr Algorithmus am Ende gut ist.

Kontrast: Bei der erwarteten Laufzeit geht es darum, wie ein Algorithmus funktioniert, es sei denn, Sie haben Pech. Wenn Sie denselben Algorithmus an derselben Eingabe aber mit unterschiedlichen Zufallsentscheidungen wiederholen, wird er möglicherweise viel schneller gelöst. Die durchschnittliche Laufzeit gibt an, wie gut ein Algorithmus bei den meisten Eingaben abschneidet. Wenn Sie denselben Algorithmus bei derselben Eingabe erneut versuchen, hilft dies nichts (es sei denn, der Algorithmus ist möglicherweise auch randomisiert).

Alex ten Brink
quelle