Memecahkan Rekurensi melalui Polinomial Karakteristik dengan Root Imajiner

Dalam analisis algoritme, Anda sering harus menyelesaikan rekurensi. Selain Master Theorem, metode substitusi dan iterasi, ada satu yang menggunakan polinomial karakteristik .

Katakanlah saya menyimpulkan bahwa polinomial karakteristik memiliki akar imajiner , yaitu dan . Maka saya tidak bisa menggunakan $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$

untuk mendapatkan solusinya, bukan? Bagaimana saya harus melanjutkan dalam kasus ini?

algorithms algorithm-analysis recurrence-relation Koray
sumber

Selamat datang! Perhatikan bahwa Anda dapat menggunakan LaTeX oleh $...$ .

Raphael

Saya bingung. Saya yakin maksud Anda metode menggunakan polinomial characteristc , bukan persamaan. Apa itu ? Solusi dari persamaan yang Anda berikan tidak imajiner, tetapi hanya irasional. Apa yang Anda maksud dengan "menerapkan [polinomial]"?

j

$j$

Raphael

Dia mengadopsi kebiasaan fisikawan salah mengeja

i

$i$

JeffE

Tentu saja Anda bisa. Pertama, solusinya memuaskan terulangnya. Kedua, ruang solusinya adalah dari dimensi 2.

Strin

Jawaban:

Ya, solusinya sebenarnya untuk beberapa konstanta dan ditentukan oleh kasus dasar. Jika case basis adalah nyata, maka (dengan induksi) semua istilah kompleks dalam akan dibatalkan, untuk semua bilangan bulat . $T(n) = \alpha(1+i)^n + \beta(1-i)^n$ $\alpha$ $\beta$ $T(n)$ $n$

Sebagai contoh, perhatikan rekurensi , dengan kasus dasar dan . Polinomial karakteristik dari pengulangan ini adalah , sehingga solusinya adalah $T(n) = 2T(n-1) - 2T(n-2)$ $T(0)=0$ $T(1)=2$ $x^2-2x+2$ untuk beberapa konstanta dan . Memasukkan case dasar memberi kita $T(n) = \alpha(1+i)^n + \beta(1-i)^n$ $\alpha$ $\beta$ yang menyiratkan

T (0) = α (1 + saya)^{0} + β (1 - saya)^{0} = α + β = 0 T (1) = α (1 + saya)^{1} + β (1 - saya)^{1} = (α + β) + (α - β) saya = 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$

yang menyiratkan

dan

. Jadi solusinya adalah

α + β = 0 α - β = - 2 saya

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

α = - i

$\alpha = -i$

β = i

$\beta = i$

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

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

Fungsi ini berosilasi antara dan $\sqrt{2}^n$ $-\sqrt{2}^n$ $T(4n) = 0$ $n$ $(1-i)^4 = (1+i)^4 = -4$ $T(0)$

JeffE
sumber

Saya sepertinya ingat bahwa akar imajiner polinomial karakteristik (yang, jika saya ingat dengan benar, fungsi singularitas yang mendominasi urutan) menyiratkan elemen negatif di suatu tempat. Benarkah? Jika demikian, aman untuk mengatakan Anda tidak boleh menemukan kasus ini dalam analisis algoritma.

Raphael

2

$2$

1 + i

$1+i$

1 - i

$1-i$

α 2^{n}

$\alpha 2^n$

α

$\alpha$