matematykaszkolna.pl
złożoność pamięciowa [algorytmy] Matt: Co prawda pytanie dotyczy algorytmów, a konkretnie złożoności pamięciowej, ale może ktoś akurat będzie weiedział. Otoż mam taki problem, niech za przykład posłuży podany niżej algorytm: function ABC(int n) begin if n < 2 return (1)
 n n 
else return (4*ABC(

) − 2*ABC(

 2 2 
end Czy dla takiego algorytmu złożoność pamięciowa to tylko zagłębienie stosu rekursji, czyli w tym przypadku wynosi ona O(2logn) = O(logn) Czy może jest to zagłębienie stosu rekursji wraz z rozmiarem danych wejściowych, za który w tym przypadku przyjmujemy liczbe bitow do zapisania naszej liczby na wejsciu(logn), czyli zlozonosc wyniesie O(2logn * logn) = O((logn)2)
8 cze 16:24
αβγδπΔΩinnerysuję
Φεθμξρςσφωηϰϱ
±
imię lub nick
zobacz podgląd
wpisz,
a otrzymasz
5^252
2^{10}210
a_2a2
a_{25}a25
p{2}2
p{81}81
Kliknij po więcej przykładów
Twój nick