Finden des Basisfalls für t (n)= t (n - a) + t (a) + cn

Question

Ich habe das Wiederauftreten mit der Rekursionsbaummethode gelöst: $$ t (n)= t (n - a) + t (a) + cn $$

Wenn ich anfing zu lösen, konnte ich die Tatsache leicht schließen, dass $ t (a) $ Gesamtkostenberechnung in Form von:

hätte

$$ H * CA $$ Aber ich konnte nicht herausfinden, wie er den Basisfall lösen kann.

Ich weiß, dass $ t (na) $ im Basisfall wäre, wenn $ n= A $ .

Aber wie man die Höhe berechnet $ H $ der Wiederholung. Ich weiß, dass der Basisfall definiert werden kann als: $$ N-IA= 0 $$

Ich habe die vorherigen Beispiele in dem Buch Einführung in Algorithmen gesehen welche Zitate:

Die Subproblem-Größe für einen Knoten in der Tiefe $ i $ ist $ n / 4 ^ i $ . Und so kam es dass der Subproblemgröße Hits $ n= 1 $ Wenn $ n / 4 ^ i= 1 $ oder äquivalent, Wenn $ i=log_4 n $

für das Wiederauftreten: $ t (n)= 3t (n / 4) + cn ^ 2 $

kommt also an den Punkt, was der Basisfall so wäre, dass die Teilproblemgröße $ n=? $ wie im obigen Beispiel fleist.

wäre es $ n= a $ ?

Bitte korrigieren Sie mich, wenn ich falsch liege. Danke.

Answer 1

Jeder $ 0 \ LE K \ LE A $ ergibt den Basisfall $ t (k) $ . Wenn Sie versuchen, das Big-o des Rezidivs zu lösen, können Sie auch annehmen, dass es ein paar $ C $ gibt, wo $ T (k) \ le c $ für jedes Basisfall $ K $ .Es wird dazu beitragen, dass die Berechnung etwas einfacher ist