notacja O duze, rekurencja

[ScottyW]

Witam,
zmagam sie z nastepujacym zadaniem:
Mam nastepujace rownanie rekurencyjne

F(n)= \(\displaystyle{ \begin{cases} n, n<=1 \\ 5*F(n-1) - 6*F(n-2), n>1 \end{cases}}\)

Nalezy pokazac ze algorytm dziala w czasie O(\(\displaystyle{ 2^n}\))

Operacja dominujaca jest mnozenie, a wiec dla n<=1 mnozen jest zero dla pozostalych sa 2, plus kolejne wywolania rekurencyjne.
Mozna to zapisac jako rownanie:
G(n)= \(\displaystyle{ \begin{cases} 0, n<=1 \\ 2 + G(n-1) + G(n-2), n>1 \end{cases}}\)

W jaki sposob pokazac ze rownanie jest zawsze ograniczone funkcja T(n) = \(\displaystyle{ 2^n}\), czyli, ze G(n) = O(T(n))


z gory dziekuje za odpowiedz
pozdrawiam
ScottyW

[Crizz]

Rozumiem, że algorytm oblicza wartość funkcji F? (tzn. jesteś pewien, że F nie miała oznaczać funkcji kosztu?).

Zakładamy, że
\(\displaystyle{ G(n-1)=O(T(n-1))}\),
\(\displaystyle{ G(n-2)=O(T(n-2))}\),
czyli istnieje takie c, dla którego
\(\displaystyle{ G(n-1) \le c2^{n-1}}\)
\(\displaystyle{ G(n-2) \le c2^{n-2}}\)
Z takich założeń wynika, ze:
\(\displaystyle{ G(n)=G(n-1)+G(n-2)+2 \le c2^{n-1}+c2^{n-2}+2=c(2^{n-1}+2^{n-2})+2 \le c2^{n}}\) - wystarczy, ze \(\displaystyle{ c \ge 1}\)

To jest dowód kroku indukcyjnego, teraz potrzeba jeszcze warunków brzegowych:
\(\displaystyle{ G(1)=0 \le c \cdot 2^{1}}\) dla dodatniego c
\(\displaystyle{ G(2)=2 \le c \cdot 2^{2}}\) dla \(\displaystyle{ c \ge \frac{1}{2}}\)

Dla \(\displaystyle{ c \ge 1}\) teza \(\displaystyle{ G(n)=O(2^{n})}\) jest spełniona dla \(\displaystyle{ n=1,n=2}\), a z prawdziwości tezy dla \(\displaystyle{ n-1,n-2}\) wynika prawdziwość tezy dla \(\displaystyle{ n}\), zatem rzeczywiście złożoność rekursji jest klasy \(\displaystyle{ O(2^{n})}\), co należało udowodnić.

[ScottyW]

Dziekuje za odpowiedz.
Tak, algorytm oblicza wartosc funkcji F.

Mialem problemy z krokiem indukcyjnym, ktory bardzo czytelnie wyjasniles.

Dzieki jeszcze raz
pozdrawiam
ScottyW