Fehler bei der Verwendung der asymptotischen Notation

10

Ich versuche zu verstehen, was mit dem folgenden Beweis der folgenden Wiederholung falsch ist

T (n) = 2 T (⌊ \frac{n}{2} ⌋) + n

$T(n) = 2\,T\!\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n$

T (n) \leq 2 (c ⌊ \frac{n}{2} ⌋) + n \leq c n + n = n (c + 1) = O (n)

$T(n) \leq 2\left(c\left\lfloor\frac{n}{2}\right\rfloor\right)+n \leq cn+n = n(c+1) =O(n)$

Die Dokumentation sagt, dass es wegen der induktiven Hypothese falsch ist, dass Was fehlt mir?

T (n) \leq c n

$T(n) \leq cn$

algorithms landau-notation asymptotics recurrence-relation Erb
quelle

2

Wiederholungen dieser Form können auch mit dem Master-Theorem gelöst werden .

Juho

2

@Ran: Ich denke nicht, dass der Master-Satz ein geeignetes Tag für diese Frage ist. Die Frage ist nicht, wie man sie löst, sondern um den Irrtum in einem bestimmten Argument aufzuzeigen. Außerdem ist der Master-Satz wahrscheinlich zu spezifisch und verdient es wahrscheinlich nicht, ein eigenes Tag zu haben. Im Allgemeinen sollten wir anhand der Frage taggen, nicht anhand möglicher Antworten. Würden Sie zum Beispiel diese Akra-Bazzi markieren?

Aryabhata

"Was ist los mit dem folgenden Beweis" - Ich sehe keinen Beweis. Es ist oft hilfreich, einen vollständigen Beweis aufzuschreiben (dh die Induktion explizit zu machen), um Fehler zu erkennen.

Raphael

Eine verwandte allgemeinere Frage ist das Lösen oder Annähern von Wiederholungsrelationen für Zahlenfolgen .

Juho

12

Nehmen wir an, das Endziel ist es, zu beweisen. Sie beginnen mit der Induktionshypothese: $T(n) = \mathcal{O}(n)$

für alle . $T(i) \leq ci$ $i < n$

Und um den Beweis zu vervollständigen, müssen Sie auch zeigen, dass . $T(n) \leq cn$

Was Sie jedoch ableiten können, ist , was für die Vervollständigung des Beweises nicht hilfreich ist. Sie benötigen eine Konstante für (fast) alle . Daher können wir nichts schließen und ist nicht bewiesen. $T(n) \leq (c+1)n$ $c$ $n$ $T(n) = \mathcal{O}(n)$

Beachten Sie, dass Sie zwischen dem Ergebnis und dem Proof-Prozess verwechselt werden. Und noch ein Punkt, ist tatsächlich $T(n)$ in diesem Fall , so dass Sie eine geeignete Induktionshypothese in Betracht ziehen können, um dies beweisen zu können. $\Theta(n \log n)$

Pad
quelle

Wenn wir c '= c + 1 ersetzen, wird sich etwas ändern?

Erb

@erb: Nein, das wird es nicht. Sie müssen für eine gewählte Konstante beweisen. Wenn Sie

ersetzen , haben Sie schließlich

(oder

), dann ist das Ergebnis dasselbe.

c^{'} = c + 1

$c'=c+1$

T (n) \leq (c^{'} + 1) n

$T(n) \leq (c'+1)n$

T (n) \leq (c + 2) n

$T(n) \leq (c+2)n$

Pad

8

Sie haben einige Schritte ausgelassen. Es sieht so aus, als würden Sie versuchen, durch Induktion zu beweisen, dass , und Ihr Beweis lautet: $T(n) = O(n)$

Angenommen, für . Dies bedeutet $T(k) = O(k)$ $k<n$ für einige . Dann ist $T(k) \le c \, k$ $c$ , also $T(n) = 2 T(\lfloor n/2\rfloor) + n \le 2 c \lfloor n/2\rfloor + n\le (c+1) \,n$ $T(n) = O(n)$ .

Dieser Beweis geht von Anfang an schief: „ für “ macht keinen Sinn. Big oh ist eine asymptotische Vorstellung: bedeutet, dass es eine Konstante und eine Schwelle N gibt, so dass $T(k) = O(k)$ $k \lt n$ $T(k) = O(k)$ $c$ . Und am Ende können Sie nicht schließen, dass „ “, weil dies etwas über die Funktion als Ganzesaussagtund Sie nur etwas über den bestimmten Wert bewiesen haben.. $\forall k \ge N, T(k) \le c \, k$ $T(n)=O(n)$ $T$ $T(n)$

Sie müssen explizit angeben, was bedeutet. Vielleicht lautet Ihr Beweis: $O$

Angenommen, $T(k) \le c \, k$ $k < n$ $T(n) = 2 T(\lfloor n/2\rfloor) + n \le 2 c \lfloor n/2\rfloor + n\le (c+1) \,n$

$T(k) \le c \, k$ $k=n$ $T(k) \le (c+1) \, k$ $T(k) \le c \, k$ $c$ $T$ $c$ $k$

$c$ $1$ $k$ $m=2^p k$ $c_m = c_k + p$ $c_k = c_0 \log_{2} k$

$k \ge 1$ $T(k) \le c \log_2(k)$

$\Theta(n\,\mathrm{log}(n))$ $O(n)$

$2T(n/2)$ $n$ $\log_2(2) = 1$ $\Theta(n\,\log(n))$

Gilles 'SO - hör auf böse zu sein'
quelle

7

Ich erweitere die bereits gegebene Antwort, vielleicht nur, indem ich meinen Kommentar ausführlicher erkläre.

$T(n) = a T(n/b) + f(n)$ $a \geq 1$ $b > 1$ $f(n)$ $\lfloor n/2 \rfloor$ $n/2$ $n/2$ Cormen et al. Buch .

$a = 2$ $b = 2$ $f(n) = \Theta(n)$ $n^{\log_b a} = n^{\log_2 2} = n$ $f(n) = \Theta (n)$ $T(n) = \Theta (n \log n)$

Juho
quelle

n = 2^{k}

$n=2^k$

Fehler bei der Verwendung der asymptotischen Notation

Antworten: