So lösen Sie das Wiederauftreten.T (n).= T (n-1) + t (n / 2) + n?

Question

Ich bin mir bewusst, dass, um eine Laufzeit mit der Rekursionsbaummethode zu erhalten, müssen wir einen Baum zeichnen und finden:

a) Anzahl der Ebenen in Baum .

Da die linke Seite des Baums um 1 in Größe abnimmt, ist der längste Weg von der Wurzel. Unterproblemgröße auf Ebene I ist generakodicetagcode. Einstellen von n - i= 1 Wenn es eine Größe von 1 trifft, erhalten wir die Anzahl der Ebenen, i= n - 1.

b) Kosten pro Knoten im Baum : generationstechniketagcode

c) Anzahl der Knoten auf Ebene i : Hier bin ich festgefahren. Nicht in der Lage, Knoten auf Ebene i zu finden, die ich seit der linken Seite um 1 abnimmt, rechte Seite um die Hälfte. Natürlich ist Baum auf der linken Seite dichter. Nicht jeder Knoten wird zwei Kinder haben.

Wenn ich eine Antwort auf c erhalten kann, kann ich t (n) berechnen= Kosten von Level 0 + Kosten von Level 1 + Kosten von Level 2 + ... Kosten der Niveau N-1. Wenn y1 die Anzahl der Knoten auf Ebene 1, y2 auf Stufe 2 usw. ist ... dann => T (n)= cn + y1 * cn + y2 * cn + y3 * cn + .... yn-1 * cn, um Gesamtkosten zu erhalten.

Kann jemand mich zum Ansatz führen, den ich nehme? ist es richtig ? Kann ich eine Annahme annehmen, dass wir für ausreichend große n T (n / 2) ignorieren können und dann fortfahren? .

Online-Suche verwirrt mich. Das Problem ist 4.4-5 von CLRs.

siehe hier

Diese Lösung sagt t (n)= o (2 ^ n) und t (n)= omega (n ^ 2) und erklärt nicht wie.

siehe auch hier

Diese Lösung sagt t (n)= o (n ^ 2). aber widerspricht der obigen Lösung

Answer 1

lass $ s (n)= t (n) - 2n - 2 $ . Sie können überprüfen, ob $ S (n)= S (N-1) + S (N / 2) $ (n / 2) $ (ignoriert die Tatsache, dass $ n / 2 $ müssen nicht eine ganze Zahl sein). Dies zeigt, dass der Additive $ n $ Begriff keinen großen Unterschied macht.

für große $ n $ , wir haben ungefähr $ s (n) - s (n-1) \ ca. S '(n) $ , und so werden wir geführt, um die Differentialgleichung zu lösen $$ S '(N)= S (N / 2). $$ Erwägen Sie $ F (n)=EXP (\ TFRAC {1} {2} \ log_2 ^ 2 n) $ . Dann $$ f '(n)=exp (\ tfrac {1} {2} \ log_2 ^ 2 n) \ cdot \ frac {\ ln n} {(\ ln 4) n}, $$ wohingegen $$ f (n / 2)=exp (\ tfrac {1} {2} (\ \ \ \ log_2 n - 1) ^ 2) \ can \ exp (\ tfrac {1} {2} \ log ^ 2 n) \ exp ( - \ log n)=exp (\ tfrac {1} {2} \ log ^ 2 n) \ cdot \ frac {1} {n}. $$ Dies deutet darauf hin, dass zumindest $ \ ln s (n)=theta (\ log ^ 2 n) $ .

woher kommt das? Sie können sich an $ s (n) $ (mit einem geeigneten Basisfall!) Als Anzahl der Möglichkeiten, von zu gehen, denken $ n $ bis Null durch Anwenden von zwei Vorgängen: Subtrahieren Sie 1 und teilen Sie ihn mit 2. Eine "typische" solche Sequenz enthält ungefähr $ \ log_2n $ Viele Operationen des zweiten Typs, aus dem $ \ theta (n) $ insgesamt, was zu der sehr groben Schätzung $ \ führt Binom {\ theta (n)} {\ \ log_2 n} $ , das auch das Formular $ \ exp \ theta (\ log ^ 2 n) $ .

---

Betrachten Sie den Konkret der folgenden genauen Definition von $ s (n) $ : Der Basisfall ist $ s (0 )= 1 $ , und für $ n> 0 $ , $$ S (n)= s (n-1) + s (\ lfloor n / 2 \ rfloor). $$ Dies ist Sequenz 000123 . Knuth, eine fast lineare Wiederholung , zeigte das $$ \ log_4 s (n) \ sim \ log_4 ^ 2 n, $$ Das heißt, das Verhältnis der beiden Begriffe neigt zu 1 als $ n \ bis \ inmTy $ . Der OEIS-Eintrag enthält noch präzisere Asymptotik.

Answer 2

Ich stimme der Fibonacci-Hypnose nicht zu, aber ich bin nicht hundertprozentig sicher meiner Antwort

Sie sehen $ t (n)= t (n-1) + c * n= o (n ^ 2) $

$ t (n)= t (n / 2) + c * n= o (n log n) $

Sie bekommen jedoch nicht t (n) mit unkomplizierter Hinzufügen.

Wenn Sie in der Rekursion eine Ebene gehen (Sie können einen Baum zeichnen)

t (n)= t (n-2) + t ((n-1) / 2) + t (n / 2-1) + t (n / 4) + [n + (n-1) + (n-1) / 2 + (n / 2-1) + n / 4]

Dies zeigt, dass es auch nicht nur ist $ o (n ^ 2) $

Ich muss es abschließen, aber ich vermute entweder $ O ((n ^ 2) * log n) $ oder $ o ((n ^ 2) * n ^ {log n})= o (n ^ 3) $

{Es gibt einen Begriff n (1 + 1/2 + 1/4 + .. 1 / n), der in den Protokoll-N-Schritten abfällt, ich muss erneut überprüfen}