Artikel

2.4: Wiederholungsbeziehungen lösen


Beispiel (PageIndex{1})

Finden Sie eine Rekursionsbeziehung und Anfangsbedingungen für (1, 5, 17, 53, 161, 485ldots ext{.})

Lösung

Das Auffinden der Wiederholungsbeziehung wäre einfacher, wenn wir einen Kontext für das Problem hätten (wie zum Beispiel den Turm von Hanoi). Leider haben wir nur die Reihenfolge. Denken Sie daran, dass die Wiederholungsbeziehung Ihnen sagt, wie Sie von vorherigen Begriffen zu zukünftigen Begriffen gelangen. Was geht hier vor sich? Wir könnten uns die Unterschiede zwischen den Termen ansehen: (4, 12, 36, 108, ldots ext{.}) Beachten Sie, dass diese um den Faktor 3 wachsen. Ist die ursprüngliche Sequenz auch? (1cdot 3 = 3 ext{,}) (5 cdot 3 = 15 ext{,}) (17 cdot 3 = 51) und so weiter. Es scheint, dass wir am Ende immer 2 weniger haben als im nächsten Semester. Aha!

Also ist (a_n = 3a_{n-1} + 2) unsere Rekursionsrelation und die Anfangsbedingung ist (a_0 = 1 ext{.})


Wiederholungsbeziehungen

EIN Wiederholungsbeziehung ist eine Gleichung, in der jeder Term der Folge als Funktion der vorhergehenden Terme definiert ist.

Es gibt verschiedene Möglichkeiten, diese Beziehungen zu lösen, die wir untersuchen werden:

Auflösen von Rekursionsbeziehungen durch wiederholte Ableitung/Substitution

Die Prämisse für diese Art von Lösung besteht darin, die Rekursionsbeziehung auf der rechten Seite kontinuierlich zu ersetzen (dh einen Wert in die ursprüngliche Gleichung einzusetzen und dann eine frühere Version der Gleichung abzuleiten). Die verschiedenen Ableitungen sollen zu einer verallgemeinerten Form der Gleichung führen, die nach einer zeitlichen Einschränkung des Algorithmus/der Gleichung gelöst werden kann: Zum Beispiel:

Die einzige an dieser Stelle verfügbare Substitution besteht darin, n durch n in der ursprünglichen Gleichung zu ersetzen:

Addiere c zu beiden Seiten, um die ursprüngliche Gleichung abzuleiten:

Nachdem nun eine andere Gleichung abgeleitet wurde, gibt es eine neue Substitution, die im Original vorgenommen werden kann: n/4 für n

Im Allgemeinen lautet die Grundgleichung:

Unter der Annahme, dass n = 2 k gilt:

Auflösen von Wiederholungsbeziehungen durch Teleskopieren

Die Voraussetzung für diese Art von Lösung ist, Werte für n zu ersetzen, die Ergebnisse zu addieren und ähnliche Terme zu eliminieren. Beispielsweise:


Die Master-Methode

Die Master-Methode ist anwendbar zum Lösen von Wiederholungen der Form
$egin T(n) = aTlinks (frac ight) + f(n) end$
wobei $a ge 0$ und $b ge 1$ Konstanten sind und $f(n)$ eine asymptotisch positive Funktion ist. Abhängig vom Wert von $a, b$ und der Funktion $f(n)$ hat die Master-Methode drei Fälle.

  1. Wenn $f(n) = O(n^)$ für eine Konstante $epsilon > 0$ ist, dann ist $T(n) = Theta(n^)$ .
  2. Wenn $f(n) = Theta(n^)$, dann ist $T(n) = Theta(n^log n)$.
  3. Wenn $f(n) = Omega(n^)$ für eine Konstante $epsilon > 0$, und wenn $af(n/b) le cf(n)$ für einige Konstante $c 0$ ist eine Konstante für $i le i le k$
  4. $b_i in (0, 1)$ ist eine Konstante für $1 le i le k$
  5. $k ge 1$ ist eine Konstante und
  6. $f(n)$ ist eine nicht negative Funktion

Die in (2) angegebene Rekursionslösung lautet:
$T(n) = Thetaleft(n^p left( 1 + int_<1>^ frac<>

> du ight) ight)$
Unter der Voraussetzung,
$sum_^a_ib_i^p = 1 ext< wobei $p$ eine eindeutige reelle Zahl ist.>$

Beispiel 1: Betrachten Sie eine Wiederholung,
$T(n) = 2T(n/4) + 3T(n/6) + Theta(nlog n)$

Für diese Wiederholung gilt $a_1 = 2, b_1 = 1/4, a_2 = 3, b_2 = 1/6, f(n) = nlog n$. Der Wert von $p$ kann wie folgt berechnet werden:
$a_1b_1^p + a_2b_2^p = 2mal (1/4)^p + 3mal (1/6)^p = 1$
$p = 1$ erfüllt die obige Gleichung. Die Lösung ist
$egin T(n) &= Thetaleft(n^p left( 1 + int_<1>^ frac<>

> du echts) echts)
& = Thetaleft(n left( 1 + int_<1>^ frac du echts) echts)
&= Thetaleft(n left( 1 + frac <2> ight ) ight)
&= Theta(nlog^2n)
Ende$


Rücksubstitutionsmethode

Bei der Vorwärtssubstitutionsmethode setzen wir $n = 0, 1, 2, …$ in die Wiederholungsbeziehung, bis wir ein Muster sehen. Bei der Rückwärtssubstitution machen wir das Gegenteil, d.h. wir setzen $n = n, n - 1, n - 2, …$ oder $n = n, n/2, n/4, …$, bis wir das Muster sehen. Nachdem wir das Muster gesehen haben, machen wir eine Vermutung für die Laufzeit und überprüfen die Vermutung. Lassen Sie uns diese Methode in einigen Beispielen verwenden.

Betrachten Sie ein Beispiel für eine Wiederholungsbeziehung unten
$T(n) = egin 1 & ext < if >n = 1 2T left (frac <2> echts) + n & ext Ende$

Gegeben $T(n)$ können wir den Wert von $T(n/2)$ aus der obigen Rekursionsbeziehung berechnen als
$T(n/2) = 2Tlinks ( frac <4> ight) + frac<2>$
Jetzt setzen wir den Wert von $T(n/2)$ zurück in $T(n)$
$T(n) = 2^2Tlinks (frac<2^2> ight ) + 2n$
Wir gehen ähnlich vor
$eginT(n) &= 2^3T links (frac <2 ^3> echts) + 3n
&= 2^4T links (frac <2^4> echts) + 4n
&= 2^kT links (frac <2^k> ight ) + kn
Ende$
Jetzt sollten wir die Randbedingung (Basisbedingung) verwenden, d.h. $T(1) = 1$. Um die Randbedingung zu verwenden, muss die Entität in $T()$ 1 sein, d.h.
$frac <2^k>= 1$
Nimmt $log_2$ auf beiden Seiten,
$n = log_2 n$
Die Gleichung (6) wird
$egin
T(n) &= 2^T links (frac<2^> ight ) + log_2 n.n
& = nT(1) + nlog_2 n
& = nlog_2 n + n
Ende$
Die Richtigkeit der obigen Laufzeit kann durch Induktion nachgewiesen werden. Setzen Sie $n = 2, 4, 8, 16, …$ und Sie können leicht überprüfen, ob die geschätzte Laufzeit tatsächlich richtig ist.

In den praktischen Fällen verwenden wir selten die Vorwärts- und Rückwärtssubstitutionsmethode. Es gibt viel ausgefeiltere und schnellere Methoden. Diese Methoden können jedoch als letzter Ausweg verwendet werden, wenn andere Methoden nicht in der Lage sind, einige Arten von Rezidiven zu lösen.


2.4: Wiederholungsbeziehungen lösen

Im vorherigen Beitrag haben wir die Analyse von Schleifen besprochen. Viele Algorithmen sind rekursiv. Wenn wir sie analysieren, erhalten wir eine Wiederholungsbeziehung für die Zeitkomplexität. Wir erhalten die Laufzeit bei einer Eingabe der Größe n als Funktion von n und die Laufzeit bei Eingaben kleinerer Größe. Zum Beispiel in Merge Sort, um ein gegebenes Array zu sortieren, teilen wir es in zwei Hälften und wiederholen den Vorgang rekursiv für die beiden Hälften. Schließlich führen wir die Ergebnisse zusammen. Die Zeitkomplexität von Merge Sort kann geschrieben werden als T(n) = 2T(n/2) + cn. Es gibt viele andere Algorithmen wie Binary Search, Tower of Hanoi usw.

Es gibt hauptsächlich drei Möglichkeiten, Rezidive zu lösen.

1) Substitutionsmethode: Wir raten für die Lösung und verwenden dann mathematische Induktion, um zu beweisen, dass die Schätzung richtig oder falsch ist.

2) Wiederholungsbaum-Methode: Bei dieser Methode zeichnen wir einen Wiederholungsbaum und berechnen die Zeit, die von jeder Baumebene benötigt wird. Abschließend fassen wir die auf allen Ebenen geleistete Arbeit zusammen. Um den Wiederholungsbaum zu zeichnen, beginnen wir mit der gegebenen Wiederholung und zeichnen weiter, bis wir ein Muster zwischen den Ebenen finden. Das Muster ist typischerweise eine arithmetische oder geometrische Reihe.

3) Meistermethode:
Die Master-Methode ist ein direkter Weg, um die Lösung zu erhalten. Die Master-Methode funktioniert nur für den folgenden Wiederholungstyp oder für Wiederholungen, die in den folgenden Typ umgewandelt werden können.

Es gibt folgende drei Fälle:
1. Wenn f(n) = O(nc) wobei c < LogBa dann T(n) = Θ(n Log B ein )

2. Wenn f(n) = Θ(n c ) wobei c = LogBa dann T(n) = Θ(n c Log n)

3.Wenn f(n) = Ω( n c ) wobei c > LogBa dann T(n) = Θ(f(n))

Wie funktioniert das?
Die Master-Methode wird hauptsächlich von der Recurrence-Tree-Methode abgeleitet. Wenn wir den Rekursionsbaum von T(n) = aT(n/b) + f(n) zeichnen, können wir sehen, dass die an der Wurzel verrichtete Arbeit f(n) und die an allen Blättern verrichtete Arbeit ist Θ(nc ) wobei c ist LogBA. Und die Höhe des Wiederholungsbaums ist LogBn

Bei der Wiederholungsbaummethode berechnen wir die gesamte geleistete Arbeit. Wenn die Arbeit an Blättern polynomiell mehr ist, dann sind Blätter der dominante Teil, und unser Ergebnis ist die Arbeit an Blättern (Fall 1). Wenn die Arbeit an Blättern und Wurzel asymptotisch gleich ist, wird unser Ergebnis die Höhe multipliziert mit der Arbeit auf jeder Ebene (Fall 2). Wenn an der Wurzel geleistete Arbeit asymptotisch mehr ist, dann wird unser Ergebnis an der Wurzel geleistete Arbeit (Fall 3).

Beispiele einiger Standardalgorithmen, deren Zeitkomplexität mit der Master-Methode bewertet werden kann
Sortieren zusammenführen: T(n) = 2T(n/2) + Θ(n). Es fällt in Fall 2, da c 1 ist und LogBa] ist auch 1. Die Lösung ist also Θ(n Logn)

Binäre Suche: T(n) = T(n/2) + (1). Es fällt auch im Fall 2, da c 0 ist und LogBa ist auch 0. Die Lösung ist also Θ(Logn)

Anmerkungen:
1) Es ist nicht notwendig, dass eine Rekursion der Form T(n) = aT(n/b) + f(n) mit dem Master-Theorem gelöst werden kann. Die angegebenen drei Fälle haben einige Lücken zwischen ihnen. Zum Beispiel kann die Wiederholung T(n) = 2T(n/2) + n/Logn nicht mit der Mastermethode gelöst werden.

2) Fall 2 kann erweitert werden für f(n) = Θ(n c Log k n)
Falls f(n) = Θ(n c Log k n) für eine Konstante k >= 0 und c = LogBa, dann T(n) = Θ(n c Log k+1 n)

Bitte schreiben Sie Kommentare, wenn Sie etwas Falsches finden oder weitere Informationen zu dem oben besprochenen Thema teilen möchten

Achtung Leser! Hören Sie jetzt auf zu lernen. Holen Sie sich alle wichtigen DSA-Konzepte mit dem DSA-Kurs im Selbststudium zu einem studentenfreundlichen Preis und werde industrietauglich. Um Ihre Vorbereitung vom Erlernen einer Sprache auf DS Algo und vieles mehr abzuschließen, lesen Sie bitte Absolvieren Sie den Vorbereitungskurs für Vorstellungsgespräche.


2.4: Wiederholungsbeziehungen lösen

Die Rekursionsbaummethode ist eine Methode zur Lösung von Rekursionsbeziehungen. Bei diesem Verfahren wird eine Rekursionsbeziehung in rekursive Bäume umgewandelt. Jeder Knoten repräsentiert die Kosten, die auf verschiedenen Rekursionsebenen angefallen sind. Um die Gesamtkosten zu ermitteln, werden die Kosten aller Ebenen aufsummiert.

  1. Zeichnen Sie einen rekursiven Baum für eine gegebene Rekursionsbeziehung
  2. Berechnen Sie die Kosten auf jeder Ebene und zählen Sie die Gesamtzahl der Ebenen im Rekursionsbaum.
  3. Zählen Sie die Gesamtzahl der Knoten im letzten Level und berechnen Sie die Kosten des letzten Levels
  4. Summiere die Kosten aller Ebenen im rekursiven Baum

Lassen Sie uns anhand einiger Beispiele sehen, wie diese Rekursionsbeziehungen gelöst werden können:

Frage 1: T(n) = 2T(n/2) + c

  • Schritt 2: Berechnen Sie die geleistete Arbeit oder die Kosten auf jeder Ebene und zählen Sie die Gesamtzahl der Ebenen im Rekursionsbaum

Rekursiver Baum mit Kosten für jedes Level

Zähle die Gesamtzahl der Level –

Wählen Sie den längsten Pfad vom Wurzelknoten zum Blattknoten

Größe des Problems auf der letzten Ebene = n/2 k

Auf der letzten Ebene wird die Größe des Problems 1

Gesamtzahl der Ebenen im rekursiven Baum = k +1 = log2(n) + 1

  • Schritt 3: Zählen Sie die Gesamtzahl der Knoten in der letzten Ebene und berechnen Sie die Kosten der letzten Ebene

T(n) = c + 2c + 4c + —- + (Anzahl der Level-1) mal + Kosten des letzten Levels

= c + 2c + 4c + —- + log2(n) mal + Θ(n)

= c(1 + 2 + 4 + —- + log2(n) mal) + Θ(n)

1 + 2 + 4 + —– + log2(n) mal –> 2 0 + 2 1 + 2 2 + —– + log2(n) mal –> Geometrische Progression (GP)

= c(n) + Θ(n)


Daher, T(n) = Θ(n)

Frage 2: T(n) = T(n/10) + T(9n/10) + n

  • Schritt 2: Berechnen Sie die geleistete Arbeit oder die Kosten auf jeder Ebene und zählen Sie die Gesamtzahl der Ebenen im Rekursionsbaum

Rekursionsbaum mit jedem Level-Kosten

Zähle die Gesamtzahl der Level –

Wählen Sie den längsten Pfad vom Wurzelknoten zum Blattknoten

(9/10) 0 n –> (9/10) 1 n –> (9/10) 2 n –> ……… –> (9/10) k n

Größe des Problems auf der letzten Ebene = (9/10) k n

Auf der letzten Ebene wird die Problemgröße 1

(9/10) k n = 1

(9/10) k = 1/n

k = log10/9(n)

  • Schritt 3: Zählen Sie die Gesamtzahl der Knoten in der letzten Ebene und berechnen Sie die Kosten der letzten Ebene

Achtung Leser! Hören Sie jetzt auf zu lernen. Üben Sie die GATE-Prüfung lange vor der eigentlichen Prüfung mit den fachbezogenen und allgemeinen Quiz, die in . verfügbar sind GATE-Testreihenkurs.


3.2. Wenn T(n) = aT(n-1) + f(n)

Dies ist ein wenig kniffliger, denn wenn die Argumente für die f-Werte fallen, werden sie mit immer mehr a-Werten multipliziert. Nach einiger Rückwärtssubstitution ist es nicht schwer, das Muster zu erkennen

Beispiel: T(n) = 2T(n-1) + n. Dann aus der Formel

Es stellt sich heraus, dass dies eine ziemlich schmerzhafte Summe ist, um sie genau zu lösen, aber wir können vernünftigerweise vermuten, dass sie irgendwo zwischen 2 n und 2 n n liegt, und versuchen, den Bereich weiter zu verkleinern, aber zu verifizieren.


Lösen nichtlinearer Beziehungen

  • Der obige Satz ist großartig, wenn Sie eine homogene lineare Rekursion haben.
    • &hellip mit deutlichen Wurzeln.
    • Und der verwandte Satz im Text kann charakteristische Gleichungen mit wiederholten Wurzeln handhaben.
    • Angenommen, wir ignorieren den nichtlinearen Teil und betrachten nur den homogenen Teil: [h_n=c_1h_ + c_2h_ + cdots + c_kh_,.]
    • Wir können das lösen und erhalten eine Formel für ().
    • Wenn wir Glück haben, finden wir vielleicht eine Lösung für () Pro manche Ausgangsbedingungen, aber vielleicht nicht die, die uns interessieren
    • Wir können den vorherigen Satz verwenden (oder einfach raten und beweisen), dass Lösungen von (h_n=3h_) haben die Form (h_n=dcdot 3^).
    • Wenn wir bereit sind, Anfangsbedingungen zu akzeptieren, können wir möglicherweise eine bestimmte Lösung finden ().
    • Wir könnten vermuten, dass es für einige Konstanten (c,d) eine lineare Lösung in der Form (p_n=cn+d) geben könnte.
    • Wir hätten recht. Es gibt eine solche Lösung genau dann für alle (n> 1): [egin p_n &= 3p_ + 2n cn+d&= 3(c(n-1)+d) + 2n cn+d&= 3cn-3c+3d+2n 0&=(2c+2)n+(2d-3c) ,. Ende] Dies gilt für alle (n) genau dann, wenn (2c+2=0) und (2d-3c=0) gilt. Wenn wir diese lösen, erhalten wir (c=-1) und (d=-3/2).
    • Wir haben eine Lösung für die Wiederholung: (p_n=-n-3/2).
    • Das ist eigentlich keine sinnvolle Lösung: Wir interessieren uns für (a_1=3) und das ist (p_1) nicht. Wir haben die falschen Anfangsbedingungen.

    Satz: Für eine Wiederholungsbeziehung in der Form [a_n=c_1a_ + c_2a_ + cdots + c_ka_ + F(n),,] wenn wir eine Lösung für den homogenen linearen Teil () (wie oben beschrieben) und eine bestimmte Lösung (), dann haben alle Lösungen der Rekursion die Form ().

    Nachweisen: Angenommen, wir haben eine Lösung für die ursprüngliche Wiederholung: (). Wir wissen das () ist auch eine Lösung: [ a_n=c_1a_ + c_2a_ + cdots + c_ka_ + F(n) p_n=c_1p_ + c_2p_ + cdots + c_kp_ + F(n) ]

    Wenn wir diese subtrahieren, erhalten wir [a_n-p_n=c_1(a_-P_) + c_2(a_-P_)+ cdots + c_k(a_-P_)] Daher, () ist eine Lösung des homogenen Teils, ().

    Also, jede Lösung () kann in der Form () für eine Lösung des homogenen Rezidivs. ∎

    • Der obige Satz sagt uns, dass alle Lösungen der Rekursion aussehen wie (a_n=dcdot 3^-n-3/2).
    • Wir müssen nur (d) ausfüllen: [egin a_1&=3 dcdot 3^<1>-1-3/2 &= 3 d&= 11/6,. Ende]
    • Wir haben schließlich (a_n=11/6cdot 3^-n-3/2).
    • Der homogene Teil davon ist (h_n=2h_). Wir könnten es erraten, aber verwenden wir das Theorem.
    • Die charakteristische Gleichung für diese Rekursion ist (r-2=0) mit Lösung (r=2). Lösungen haben also die Form (h_n=dcdot2^n).
    • Schätzen Sie für eine bestimmte Lösung, dass (p_n=ccdot 3^n) für einige (c) gilt. Wir können die Vermutung bestätigen, indem wir eine Konstante (c) finden. Dazu setzen wir in die Wiederholung ein: [egin p_n &= 2p_+3^n ccdot 3^n &= 2(ccdot 3^)+3^n c(3^n-2cdot 3^) &= 3^n c(3-2) &= 3^n/3^ c&=3,. Ende]
    • Wir haben eine bestimmte Lösung (für keine bestimmten Anfangsbedingungen) von (p_n=3^).
    • Nun können wir (a_n) für unsere Anfangsbedingung erfüllen, da alle Lösungen von () haben die Form [egin a_n &= d2^n + 3^ 5=a_1 &= d2^1 + 3^2 5 &= 2d+3 d&=2,. Ende]
    • Also, (a_n=2^+ 3^).
    • Der homogene Teil hat die charakteristische Gleichung (r^2-5r-6=0), also Wurzeln (r_1=6,r_2=-1).
    • Lösungen haben also die Form (h_n=d_1 6^n+d_2 (-1)^n).
    • Für eine bestimmte Lösung sollten wir etwas in der Form (p_n=ccdot 7^n) finden: [egin p_n = ccdot 7^n &= 5ccdot 7^+6ccdot 7^+7^n ccdot 7^2 &= 5ccdot 7^1+6ccdot 7^0+7^2 0 &= 49/8,. Ende]
    • Wir haben also (p_n=frac<49><8>cdot 7^n).
    • Aus dem Satz, [a_n=d_1 6^n+d_2 (-1)^n+ frac<49><8>cdot 7^n,.]
    • Durch Ersetzen von (a_0) und (a_1) erhalten wir [ 1=d_1+d_2+ frac<49><8> ext < und >6=6d_1-d_2+ frac<343><8>, , d_1=-6 ext < und >d_2= frac<7><8>,. ]
    • Damit haben wir eine Lösung: [a_n= -6cdot 6^n- frac<7><8>cdot (-1)^n+ frac<49><8>cdot 7^n = frac <1><8>left(-8cdot 6^ - 7(-1)^n + 7^Rechts) ,.]
    • Ohne das Theorem wäre ich definitiv nicht darauf gekommen.

    4. Der Meistersatz

    Das Master-Theorem liefert sofortige asymptotische Lösungen für viele Rekursionen der Form T(n) = aT(n/b) + f(n), die für alle Werte von n (nicht nur Potenzen von b) gelten. Es basiert auf der Anwendung der Analyse des vorherigen Abschnitts auf verschiedene breite Familien von Funktionen f und der anschließenden Erweiterung der Ergebnisse unter Verwendung eines Monotoniearguments auf Werte von n, die keine Potenzen von b sind. Hier skizzieren wir den Beweis, siehe LevitinBook Anhang B für eine detailliertere Argumentation.

    Wenn f(n) = 0, dann ist die Wiederholung einfach T(n) = aT(n/b). Dies hat die Lösung T(n) = n log[b] a T(1) = Θ(n log[b] a ). (Beispiel: T(n) = 4T(n/2) hat Lösung Θ(n lg 4 ) = Θ(n²).) Wir klassifizieren verschiedene Fälle des Hauptsatzes basierend darauf, wie f(n) im Vergleich zu dieser Standardlösung abschneidet.

    Wir nehmen durchgängig T(1) = Θ(1) an.

    Angenommen, f(x) = x c . Dann ist a i f(n/b i ) = a i n c / b ic = n c (a/b c ) i . Die Summe ist dann eine geometrische Reihe mit Verhältnis (a/b c ) und ihr Verhalten hängt entscheidend davon ab, ob (a/b c ) kleiner 1, gleich 1 oder größer als 1 ist.

    Wenn (a/b c ) kleiner als 1 ist, dann Sigmai=0 bis unendlich nc (a/bc) i = nc/(1-(a/bc)) = O(nc). Dieser Fall tritt auf, wenn log(a/b c ) = log a - c log b kleiner als Null ist, was genau dann auftritt, wenn c > log a / log b = logB A. Wenn also f(n) = nc ist, dominiert der f(n)-Term in der Summe sowohl den Rest der Summe als auch den n log[b] a-Term, und wir erhalten T(n) = Θ(f(n)) . Wenn f(n) Omega(nc ) ist, aber die zusätzliche technische Anforderung erfüllt, dass af(n/b) <= (1-Delta) f(n) für alle n und ein festes Delta > 0 ist, dann ist das geometrische Reihenargument funktioniert immer noch mit Faktor (1-Delta), und wir erhalten immer noch T(n) = Θ(f(n)). Dies deckt den Fall ab, in dem f(n) = Omega(n log[b] a + epsilon) gilt.

    Wenn (a/b c ) gleich 1 ist, dann ist jeder Term in der Summe gleich und die Summe ist f(n) logB n. In diesem Fall c = logB a, also f(n) = n log[b] a und f(n) logB n dominiert (kaum) den T(1)-Term. Eine erweiterte Version dieser Analyse zeigt, dass die Lösung T(n) = Θ(f(n) log n) ist, wenn f(n) = Θ(n log[b] a ).

    Wenn schließlich (a/b c ) größer als 1 ist, haben wir eine geometrische Reihe, deren Summe proportional zu ihrem letzten Term ist, von dem gezeigt werden kann, dass er asymptotisch kleiner ist als der T(1)-Term. Dieser Fall ergibt T(n) = Θ(n log[b] a ) für jedes f(n) = O(n log[b] a – epsilon).

    Diese drei Fälle decken nicht alle Möglichkeiten ab (betrachten Sie T(n) = 2T(n/2) + n log n), aber sie behandeln die meisten Wiederholungen dieser Form, denen Sie wahrscheinlich begegnen werden.


    Dies scheint der richtigen Antwort ziemlich nahe zu kommen.

    Wenn $k = lceil ln(n)/ln(7) ceil$, $n le 7^k$, also $A(lceil n/7^k ceil) = 1$ ist.

    Setzen Sie dies in Ihre Gleichung ein, $A(n) = 4^k +4^klfloor n/7^k floor ^2 . +4lEtage n/7 Etage ^2 + n^2 $.

    Um eine obere Schranke zu erhalten, da $lfloor x floor le x le lceil x ceil < x+1$, $4^k < 4^ <1+ln(n)/ln(7)> = 4n^ < 4n $ also $A(n) < 4n + n^2(4^k/7^k+. +4/7+1) < 4n + n^2/(1-4/7) < 4n + 7 n^2/3 $.

    In diesem Fall konvergiert die Reihe, die $n^2$ multipliziert.

    Versuchen Sie dies mit den vertauschten 4 und 7 zu lösen, sodass $A()=7A(lfloor floor)+n^2$.


    Schau das Video: Mini refrigerator Kemin KM-20L-A, 20L. из Китая (November 2021).