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
notacja O duze, rekurencja
-
- Użytkownik
- Posty: 4094
- Rejestracja: 10 lut 2008, o 15:31
- Płeć: Mężczyzna
- Lokalizacja: Łódź
- Podziękował: 12 razy
- Pomógł: 805 razy
notacja O duze, rekurencja
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ć.
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ć.
-
- Użytkownik
- Posty: 4
- Rejestracja: 26 lis 2009, o 21:25
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 1 raz
notacja O duze, rekurencja
Dziekuje za odpowiedz.
Tak, algorytm oblicza wartosc funkcji F.
Mialem problemy z krokiem indukcyjnym, ktory bardzo czytelnie wyjasniles.
Dzieki jeszcze raz
pozdrawiam
ScottyW
Tak, algorytm oblicza wartosc funkcji F.
Mialem problemy z krokiem indukcyjnym, ktory bardzo czytelnie wyjasniles.
Dzieki jeszcze raz
pozdrawiam
ScottyW