Wie verwende ich gegnerische Argumente für die Auswahl und Einfügungssortierung?

Ich wurde gebeten, die gegnerischen Argumente zu finden, die notwendig sind, um die unteren Grenzen für die Auswahl und die Einfügungssortierung zu finden. Ich konnte nirgendwo einen Hinweis darauf finden.

Ich habe einige Zweifel. Ich verstehe, dass gegnerische Argumente normalerweise verwendet werden, um Untergrenzen für bestimmte "Probleme" und nicht für "Algorithmen" zu finden.

Ich verstehe das Zusammenführungsproblem. Aber wie könnte ich eine zur Auswahl und Einfügungssortierung schreiben?

algorithms algorithm-analysis proof-techniques lower-bounds user5507
quelle

Hinweis: Für einen Gegner ist es viel einfacher, einen bekannten Algorithmus zu täuschen als für alle Algorithmen.

Raphael

@ Raphael Ich weiß, dass es einfach ist, da der Gegner den Algorithmus kennt, den er im schlimmsten Fall kennt, in dem sich der Algorithmus verhält. Im Fall der Auswahl- / Einfügungssortierung ist die Komplexität also O (n ^ 2), die Untergrenze wäre die selbst? Ich bin wenig verwirrt über einen bestimmten Algorithmus. Untergrenze bedeutet die Untergrenze im schlimmsten Fall?

user5507

@ user5507: Ja, normalerweise werden kontroverse Argumente vorgebracht, um eine Untergrenze für eine ganze Klasse von Problemen zu beweisen, nicht für einen bestimmten Algorithmus. In diesem Fall müssen Sie nur die Strategie für den Gegner angeben, die die Worst-Case-Eingabe für diese beiden Algorithmen ergibt.

Peter

"Gegner" bedeutet in dieser Einstellung einfach "Worst-Case-Eingabe".

JeffE

Antworten:

$\Theta(n)$ $\Theta(n^2)$ $n$ $n$ $\Omega(n)$ $O(n^2)$ $\Omega(n^2)$ $O(n)$ $\Omega(n^2)$ $\Omega(n^2)$ $O$

Lassen Sie uns nun über ein gegnerisches Argument für die Einfügesortierung nachdenken (Sie können versuchen, eines für die Auswahlsortierung abzuleiten, indem Sie dieselben Ideen anwenden).

Betrachten Sie den Insertion Sort-Algorithmus, der gegen einen Gegner spielt, den wir den Gegner nennen werden. Das Ziel des Gegners ist es, eine Eingabe X für den Algorithmus bereitzustellen, die die Anzahl der vom Algorithmus durchgeführten Vergleiche maximiert. Dies wird normalerweise im Zusammenhang mit Entscheidungsbäumen analysiert . Ein Entscheidungsbaum zeigt alle möglichen Sequenzen von Vergleichen, die der Algorithmus durchführen könnte. Jeder innere Knoten eines Entscheidungsbaums repräsentiert einen einzelnen Vergleich. Die beiden Kinder eines Knotens repräsentieren die beiden Ergebnisse des Vergleichs (Ja / Nein oder Richtig / Falsch). Jedes Blatt repräsentiert eine mögliche Ausgabe. Für Sortieralgorithmen sind die Blätter Permutationender Schlüssel. Der Algorithmus beginnt an der Wurzel und folgt einem Pfad bis zu einem Blatt. An jedem internen Knoten teilt die Antwort für den durchgeführten Vergleich dem Algorithmus mit, welcher Knoten als nächstes besucht werden muss. Wenn der Algorithmus ein Blatt erreicht, gibt er seine entsprechende Permutation aus. Die Laufzeit eines Algorithmus (als Entscheidungsbaum betrachtet) für eine bestimmte Eingabe ist die Anzahl der Vergleiche, die auf dem Pfad von der Wurzel zum Ausgabeblatt durchgeführt werden. Jetzt hat der Gegner eine einfache Strategie, die gegen jeden vergleichsbasierten Sortieralgorithmus funktioniert, einschließlich der Einfügungssortierung: Wenn der Algorithmus einen Vergleich durchführt, wählt der Gegner die Antwort, die die geringstmöglichen Permutationen eliminiert.

$n$ $n!$ $n!$ $\Omega(\log(n!)) = \Omega(n\log n)$ $\Omega(n^2)$

$A[1 .. n]$

$A[1 .. j-1]$ $A[1 .. j-1]$

$A[1 .. j-1]$ $A[j]$ $A[j]$ $A[1 .. j-1]$ $A[j-1]$ $A[j-2]$ $A[j]$ $A[j+1 .. n]$

$A[j]$ $A[1 .. j-1]$ $j$ $A[j]$ $j-1$ $\Omega(n^2)$

Massimo Cafaro
quelle

tl; dr: Die Strategie des Gegners besteht darin, ein umgekehrt sortiertes Array als Eingabe zu präsentieren und dann irgendwo am Strand abzuhängen, ein paar Drinks zu trinken und vielleicht das Surfen zu lernen.

JeffE