Obliczenie złożoności pamięciowej

bartekw2213
Użytkownik
Użytkownik
Posty: 60
Rejestracja: 1 paź 2020, o 16:18
Płeć: Mężczyzna
wiek: 20
Podziękował: 33 razy

Obliczenie złożoności pamięciowej

Post autor: bartekw2213 »

Hej, muszę obliczyć złożoność pamięciową poniższej funkcji

Kod: Zaznacz cały

function A(n:integer);
if n < 2 then A := 1 else A:=A(n/3) + A(n/3) + n * n;
Oszacowałem, że liczba wykonywanych kroków podczas wywołania funkcji to \(\displaystyle{ n^{\log_3{4}} }\)

Jednak czy mamy tutaj jakąkolwiek dodatkowo alokowaną pamięć poza miejscem na stosie na dodatkowe wywołania funkcji?
Czy zatem złożoność pamięciowa nie będzie równa ilości wykonywany kroków (czyli wywołań rekurencyjnych)?
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Obliczenie złożoności pamięciowej

Post autor: Dasio11 »

Liczba kroków to asymptotycznie \(\displaystyle{ n^{\log_3 2}}\), nie \(\displaystyle{ n^{\log_3 4}}\), a złożoność pamięciowa to asymptotycznie \(\displaystyle{ \log_3 n}\).

Strukturę rekurencyjnych wywołań funkcji można zilustrować jako drzewo binarne, którego węzłami są pojedyncze wywołania. Każde takie wywołanie albo nie powoduje kolejnych (gdy n<2) i odpowiada mu liść w tym drzewie, albo powoduje dwa kolejne, i odpowiada mu węzeł wewnętrzny w drzewie, którego dwoje dzieci to te właśnie zagnieżdżone wywołania. Korzeniowi drzewa odpowiada oryginalne wywołanie.

Z tego obrazka jasno widać, że liczba kroków w algorytmie równa jest (z dokładnością do stałej) liczbie węzłów drzewa, których, jak nietrudno obliczyć, jest mniej-więcej \(\displaystyle{ 2^{\log_3 n} = n^{\log_3 2}}\). Z kolei złożoność pamięciowa to z grubsza wysokość drzewa, bo będąc w dowolnym węźle drzewa, musimy pamiętać na stosie ramki dla wszystkich "nadwywołań", a one leżą na ścieżce od obecnego węzła do korzenia. Znów nietrudno wyliczyć, że tą wysokością jest około \(\displaystyle{ \log_3 n}\) i stąd wynika powyższe szacowanie na złożoność pamięciową.
ODPOWIEDZ