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?
Złożoność algorytmu rozwiązującego problem wież w Hanoi
-
- 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
Wiem, że to potęgowanie! Chodzi mi o to, co mam podstawić za te epsilon... W praktyce co to oznacza. To jakiś szereg?
- paladin
- 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
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)}\).
-
- 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
Po przeanalizowaniu kilku przkładów wynika, że masz rację paladin. Dziękuję