Złożoność algorytmu rozwiązującego problem wież w Hanoi

rudolf35
Użytkownik
Użytkownik
Posty: 18
Rejestracja: 10 paź 2007, o 19:38
Płeć: Mężczyzna
Lokalizacja: Toruń
Podziękował: 6 razy

Złożoność algorytmu rozwiązującego problem wież w Hanoi

Post autor: rudolf35 »

Równanie w obliczaniu złożoności problemu wież w Hanoi ma postać
T(n)=2T(n-1)+10
na mocy twierdzenia złożoność algorytmu typu "jeden krok w tył" wynosi \(\displaystyle{ \theta(2^n)}\), ponieważ gdy \(\displaystyle{ d(n) = O( \frac{a^n}{n^ \epsilon })}\) to złożoność wynosi \(\displaystyle{ \theta(a^n)}\). Nie rozumiem tego twierdzenia. Co oznacza to epsilon nad n?
Awatar użytkownika
Zordon
Użytkownik
Użytkownik
Posty: 4977
Rejestracja: 12 lut 2008, o 21:42
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 75 razy
Pomógł: 910 razy

Złożoność algorytmu rozwiązującego problem wież w Hanoi

Post autor: Zordon »

potęgowanie?
rudolf35
Użytkownik
Użytkownik
Posty: 18
Rejestracja: 10 paź 2007, o 19:38
Płeć: Mężczyzna
Lokalizacja: Toruń
Podziękował: 6 razy

Złożoność algorytmu rozwiązującego problem wież w Hanoi

Post autor: rudolf35 »

Wiem, że to potęgowanie! Chodzi mi o to, co mam podstawić za te epsilon... W praktyce co to oznacza. To jakiś szereg?
Awatar użytkownika
paladin
Użytkownik
Użytkownik
Posty: 148
Rejestracja: 24 sty 2005, o 22:15
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 19 razy

Złożoność algorytmu rozwiązującego problem wież w Hanoi

Post autor: paladin »

Nie bardzo wiem, jak sformułowane jest twierdzenie, o które chodzi, ale podejrzewam taką interpretację: jeśli można dobrać taki wykładnik \(\displaystyle{ \epsilon > 0}\), dla którego \(\displaystyle{ d(n) = O( \frac{a^n}{n^ \epsilon })}\) to złożoność wynosi \(\displaystyle{ \theta(a^n)}\).
rudolf35
Użytkownik
Użytkownik
Posty: 18
Rejestracja: 10 paź 2007, o 19:38
Płeć: Mężczyzna
Lokalizacja: Toruń
Podziękował: 6 razy

Złożoność algorytmu rozwiązującego problem wież w Hanoi

Post autor: rudolf35 »

Po przeanalizowaniu kilku przkładów wynika, że masz rację paladin. Dziękuję
ODPOWIEDZ