Zaawansowane algorytmy i struktury danych/Ćwiczenia 13

Zadanie ?

Uzasadnić dlaczego algorytm $A_{k+1}$ liczenia minimum działa w czasie O(1) używając $P_{k+1}(n))$ procesor"ow, gdzie $P_k(n)=n^{1+{ϵ}_k},{ϵ}_k=\frac{1}{2^k-1}$

Rozwiazanie

$\max \{(\frac{n}{n^{\alpha }}{)}^{1+{ϵ}_k},\frac{n}{n^{\alpha }}\times (n^{\alpha }{)}^{1+{ϵ}_k}\}=O(P_{k+1}(n))$

gdzie $\alpha =\frac{1}{2^k+1}$

Zadanie ?

Oblicz minimum w tablicy n-elementowej w czasie O(log log n) używając O(n / log log n) procesorół.

Rozwiazanie

Dzeilimy tablicę na kawałki długości $\sqrt{n}$. Z otrzymanymi kawałkami robimy to samo, aż długość będzie pewną stałą.