rekurencjny algorytm dla danych rozmiaru n<=2 wykonuje stala liczbe krokow natomiast dla wiekszych rozmiarow danych:
-w czasie theta (n) generuje 2 podzadania wielkosci w przyblizeniu n/2
-rozwiazuje podzadania rekurencyjnie
-scala wyniki podzadan w stalym czasie
a) Napisz równanie rekurencyjne opisujace zlozonosc algorytmu
b) Korzystajac z ogolnego twierdzenia podaj wzor na funkcje zlozonosci uzywjac odpowiedniego symbolu notacji " o duze i podobne"
c)
wersja 2 tego algorytmu rozni sie tylko faza scalania wynikow podzadan ktora w wersji 2 potrzebuje theta( n kwadrat ) kroków. jaka jest zlozonsoc wersji 2
0
0
Rownanie:
T(n) = T(n/2) * 2 + A; A = const
Zlozonosc: O(n log n).
Punkt c) jest ciekawy. Na pewno trywialne oszacowanie dolne to O(n^2),
gorne to O(n2 log n). Stawiam na O(n2), ale nie poparlem tego obliczeniami a jedynie programistyczna intuicja... [green]
0
hmm, z tw. o rekurencji uniwersalnej wydaje sie, ze rzeczywiscie n2 jest asymptotycznie dokladnym oszacowaniem dla funkcji w c) czyli spelniajacej rownianie: f(n)=2*f(n-1)+n2