Rozwiązywanie nawrotów za pomocą charakterystycznego wielomianu z wyobrażonymi korzeniami

W analizie algorytmów często trzeba rozwiązywać nawroty. Oprócz Twierdzenia Mistrza, metod podstawiania i iteracji, istnieje jedna z charakterystycznymi wielomianami .

Powiedzieć, że stwierdzono, że wielomian charakterystyczny ma urojoną korzenie, mianowicie i . Więc nie mogę użyć $x^2 - 2x + 2$ $x_1 = 1+i$ $x_2 =1-i$

$\qquad c_1\cdot x_1^n + c_2\cdot x_2^n$

uzyskać rozwiązanie, prawda? Jak mam postępować w tej sprawie?

algorithms algorithm-analysis recurrence-relation Koray
źródło

Witamy! Pamiętaj, że możesz używać LaTeX przez $...$ .

Raphael

Jestem zdezorientowany. Jestem pewien, że masz na myśli metodę wykorzystującą wielomiany charakterystyczne , a nie równania. Co to jest ? Rozwiązania równania, które podajesz, nie są urojone, ale jedynie irracjonalne. Co rozumiesz przez „zastosuj [wielomian]?

j

$j$

Raphael

On przyjął habit fizyk dotyczącą zapisać z błędem .

i

$i$

JeffE

Oczywiście możesz. Po pierwsze, rozwiązanie spełnia kryteria ponownego wystąpienia. Po drugie, przestrzeń rozwiązania ma wymiar 2.

Strin

Odpowiedzi:

Tak, rozwiązaniem jest w rzeczywistości dla niektórych stałych i określonych przez przypadki podstawowe. Jeśli przypadki bazowe są prawdziwe, wówczas (przez indukcję) wszystkie złożone wyrażenia w zostaną anulowane, dla wszystkich liczb całkowitych . $T(n) = \alpha(1+i)^n + \beta(1-i)^n$ $\alpha$ $\beta$ $T(n)$ $n$

Na przykład rozważ wznowienie , z przypadkami podstawowymi i . Charakterystyczny wielomian tego nawrotu to , więc rozwiązaniem jest dla niektórych stałych i . Podłączenie przypadków bazowych daje nam co oznacza co oznacza i . Więc rozwiązaniem jest $T(n) = 2T(n-1) - 2T(n-2)$ $T(0)=0$ $T(1)=2$ $x^2-2x+2$ $T(n) = \alpha(1+i)^n + \beta(1-i)^n$ $\alpha$ $\beta$

T (0) = α (1 + i)^{0} + β (1 - i)^{0} = α + β = 0 T (1) = α (1 + i)^{1} + β (1 - i)^{1} = (α + β) + (α - β) i = 2

$T(0) = \alpha(1+i)^0 + \beta(1-i)^0 = \alpha+\beta = 0\\ T(1) = \alpha(1+i)^1 + \beta(1-i)^1 = (\alpha+\beta) + (\alpha-\beta)i = 2$

α + β = 0 α - β = - 2 i

$\alpha + \beta = 0 \\ \alpha - \beta = -2i$

α = - i

$\alpha = -i$

β = i

$\beta = i$

T (n) = i \cdot ((1 - i)^{n} - (1 + i)^{n}) .

$T(n) = i\cdot ((1-i)^n - (1+i)^n).$

Ta funkcja oscyluje między a z „kropką” 4. W szczególności mamy dla wszystkich , ponieważ (i ponieważ ostrożnie wybrałem podstawowy przypadek ). $\sqrt{2}^n$ $-\sqrt{2}^n$ $T(4n) = 0$ $n$ $(1-i)^4 = (1+i)^4 = -4$ $T(0)$

JeffE
źródło

Wydaje mi się, że pamiętam, że wyobrażone korzenie charakterystycznego wielomianu (które, jeśli dobrze pamiętam, dominujące osobliwości funkcji generującej sekwencję) sugerują gdzieś elementy negatywne. Czy to prawda? Jeśli tak, można śmiało powiedzieć, że nigdy nie powinieneś spotkać się z tym przypadkiem w analizie algorytmu.

Raphael

Niekoniecznie. Jeśli na przykład pierwiastki funkcji charakterystycznej to , oraz , funkcja będzie oscylować wokół dla niektórych , ale (przy odpowiednich przypadkach bazowych) zawsze będzie dodatnia.

2

$2$

1 + i

$1+i$

1 - i

$1-i$

α 2^{n}

$\alpha 2^n$

α

$\alpha$

JeffE