In der Algorithmusanalyse müssen Sie häufig Wiederholungen lösen. Zusätzlich zu den Master-Theorem-, Substitutions- und Iterationsmethoden gibt es eine, die charakteristische Polynome verwendet .
Angenommen , I geschlossen habe , daß ein charakteristisches Polynom hat imaginäre Wurzeln, nämlich und . Dann kann ich nicht verwenden
um die Lösung zu erhalten, richtig? Wie soll ich in diesem Fall vorgehen?
$...$
.Antworten:
Ja, die Lösung ist tatsächlich für einige Konstanten und die durch die bestimmt werden. Wenn die Basen Fällen reell sind, dann (durch Induktion) alle komplexen Terme in wird abbrechen, für alle ganzzahligen .T(n)=α(1+i)n+β(1−i)n α β T(n) n
Betrachten Sie zum Beispiel die Wiederholung mit den Basisfällen und . Das charakteristische Polynom dieser Wiederholung ist , daher lautet die Lösung für einige Konstanten und . Das Einstecken von Basisfällen ergibt was was impliziert und . Die Lösung ist alsoT(n)=2T(n−1)−2T(n−2) T(0)=0 T(1)=2 x2−2x+2 T(n)=α(1+i)n+β(1−i)n α β
Diese Funktion oszilliert zwischen und mit einer "Periode" von 4. Insbesondere haben wir für alle , weil (und weil ich den Basisfall sorgfältig ausgewählt habe).2–√n −2–√n T(4n)=0 n (1−i)4=(1+i)4=−4 T(0)
quelle