Untergrenze des Algorithmus zur Lösung bestimmter Wiederholungen

Nov 20 2020

Ich muss die Untergrenze der folgenden Rekursion finden:

$A_1 = C_1 = p_1$, $B_1 = D_1 = 1-p_1$, $F_k = A_k + B_k$. Bewerten$F_n$. \begin{align} A_{k+1} &= (A_k + 2C_k) p_{k+1} + (1-p_k) p_{k+1}, \\ B_{k+1} &= (B_k + 2D_k) (1-p_{k+1}) + p_k (1-p_{k+1}), \\ C_{k+1} &= C_k p_{k+1} + (1-p_k) p_{k+1}, \\ D_{k+1} &= D_k (1-p_{k+1}) + p_k (1-p_{k+1}). \end{align}

In diesem Fall alle Nummern des Formulars $p_i$ erhalten Eingaben (gibt es $n$ von ihnen).

Ich muss die Untergrenze dieses Algorithmus finden.

Da ist es gerade Laufzeit $O(n)$ (richtig?), ich weiß mit Sicherheit, dass der maximal mögliche Wert der Untergrenze ist $\Omega(n)$. Wie würde ich das beweisen / widerlegen?$\Omega(n)$ ist wirklich die minimale Grenze und das $\Omega(n-1)$ ist nicht / ist erreichbar?

Die einzige Hauptmethode, die ich kenne, um solche Dinge zu beweisen, ist ein gegnerisches Argument, aber nach ein paar Stunden des Nachdenkens konnte ich immer noch kein Argument finden, um zu beweisen, was ich will.

Alle Hilfen / Tipps / Vorschläge wäre sehr dankbar.

Antworten

YuvalFilmus Nov 20 2020 at 14:49

Hier herrscht große Verwirrung:

  1. $\Omega(n)$ und $\Omega(n-1)$ sind absolut gleich.
  2. Sie sind kein gegnerisches Argument, um zu zeigen, dass dieser Algorithmus ausgeführt wird $\Theta(n)$. Es folgt unmittelbar aus der Beschreibung des Arguments.
  3. Es gibt einen Unterschied zwischen der Analyse der Laufzeit eines bestimmten Algorithmus und der Darstellung, dass jeder Algorithmus, der ein Problem korrekt löst, in mindestens so vielen Schritten ausgeführt werden muss.

Um zu zeigen, dass jeder Algorithmus berechnet$F_n$ richtig muss rechtzeitig laufen $\Omega(n)$Wir werden zeigen, dass ein solcher Algorithmus alle Eingaben lesen muss $p_1,\ldots,p_n$. Ausgangspunkt ist folgende Beobachtung:

Die korrekte Ausgabe ist für die Instanzen unterschiedlich $p_1=\cdots=p_n=0$ und $p_1=\cdots=p_{i-1}=0,p_i=1,p_{i+1}=\cdots=p_n=0$.

Angesichts dessen können wir ein einfaches gegnerisches Argument verwenden, um zu zeigen, dass jeder Algorithmus, der die Funktion korrekt berechnet, alle lesen muss $p_j$. Führen Sie den angegebenen Algorithmus aus und antworten Sie$0$ wann immer es den Wert von einigen abfragt $p_j$. Wenn die Antwort ohne Abfrage angekündigt wird, sagen Sie:$p_i$Dann kann es die beiden oben genannten Fälle nicht unterscheiden, und insbesondere wird seine Antwort bei mindestens einem von ihnen falsch sein.