szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna
PostNapisane: 11 sty 2010, o 21:39 
Użytkownik

Posty: 4
Lokalizacja: Warszawa
Witam,
zmagam sie z nastepujacym zadaniem:
Mam nastepujace rownanie rekurencyjne

F(n)= \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(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)= \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) = 2^n, czyli, ze G(n) = O(T(n))


z gory dziekuje za odpowiedz
pozdrawiam
ScottyW
Góra
Mężczyzna
PostNapisane: 11 sty 2010, o 22:19 
Gość Specjalny

Posty: 4094
Lokalizacja: Łódź
Rozumiem, że algorytm oblicza wartość funkcji F? (tzn. jesteś pewien, że F nie miała oznaczać funkcji kosztu?).

Zakładamy, że
G(n-1)=O(T(n-1)),
G(n-2)=O(T(n-2)),
czyli istnieje takie c, dla którego
G(n-1) \le c2^{n-1}
G(n-2) \le c2^{n-2}
Z takich założeń wynika, ze:
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 c \ge 1

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

Dla c \ge 1 teza G(n)=O(2^{n}) jest spełniona dla n=1,n=2, a z prawdziwości tezy dla n-1,n-2 wynika prawdziwość tezy dla n, zatem rzeczywiście złożoność rekursji jest klasy O(2^{n}), co należało udowodnić.
Góra
Mężczyzna
PostNapisane: 11 sty 2010, o 22:32 
Użytkownik

Posty: 4
Lokalizacja: Warszawa
Dziekuje za odpowiedz.
Tak, algorytm oblicza wartosc funkcji F.

Mialem problemy z krokiem indukcyjnym, ktory bardzo czytelnie wyjasniles.

Dzieki jeszcze raz
pozdrawiam
ScottyW
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Rekurencja liniowa - zadanie 4  suchy1111  2
 Rekurencja z mnożeniem dwóch poprzednich wyrazów  Konikov  2
 rekurencja i funkcja tworzaca  Gogeta  8
 Dowodzenie równości z notacją "duże O"  Shelim  4
 Rekurencja liniowa rzędu I  MenosGrandes  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl