Matematyka.pl

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?

potęgowanie?

Wiem, że to potęgowanie! Chodzi mi o to, co mam podstawić za te epsilon... W praktyce co to oznacza. To jakiś szereg?

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)}\).

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