Lösen von Wiederholungen über ein charakteristisches Polynom mit imaginären Wurzeln

9

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 verwendenx22x+2x1=1+ix2=1i

c1x1n+c2x2n

um die Lösung zu erhalten, richtig? Wie soll ich in diesem Fall vorgehen?

Koray
quelle
Herzlich willkommen! Beachten Sie, dass Sie LaTeX von verwenden können $...$.
Raphael
1
Ich bin verwirrt. Ich bin sicher, Sie meinen die Methode mit charakteristischen Polynomen , nicht mit Gleichungen. Was ist ? Die Lösungen der Gleichung, die Sie geben, sind nicht imaginär, sondern nur irrational. Was meinst du mit "das [Polynom] anwenden"? j
Raphael
6
Er hat die Angewohnheit des Physikers übernommen, falsch zu . i
JeffE
Natürlich kannst du das tatsächlich. Erstens erfüllt die Lösung das Wiederauftreten. Zweitens hat der Lösungsraum die Dimension 2.
Strin

Antworten:

12

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+β(1i)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 also T(n)=2T(n1)2T(n2)T(0)=0T(1)=2x22x+2T(n)=α(1+i)n+β(1i)nαβ

T(0)=α(1+i)0+β(1i)0=α+β=0T(1)=α(1+i)1+β(1i)1=(α+β)+(αβ)i=2
α+β=0αβ=2i
α=iβ=i
T(n)=i((1i)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).2n2nT(4n)=0n(1i)4=(1+i)4=4T(0)

JeffE
quelle
1
Ich scheine mich zu erinnern, dass imaginäre Wurzeln des charakteristischen Polynoms (die, wenn ich mich richtig erinnere, die dominierenden Singularitäten der Erzeugungsfunktion der Sequenz sind) irgendwo negative Elemente implizieren. Ist das wahr? Wenn ja, können Sie mit Sicherheit sagen, dass Sie diesen Fall bei der Algorithmusanalyse niemals antreffen sollten.
Raphael
6
Nicht unbedingt. Wenn die Wurzeln der charakteristischen Funktion beispielsweise , und , schwingt die Funktion für einige um , ist aber (mit geeigneten Basisfällen) immer positiv. 21+i1iα2nα
JeffE