Zaawansowane algorytmy i struktury danych/Ćwiczenia 13: Różnice pomiędzy wersjami

Wersja z 10:43, 30 sie 2006

Zadanie ?

Uzasadnić dlaczego algorytm $A_{k+1}$ liczenia minimum dzia"la w czasie $O(1)$ używając $P_{k + 1} (n))$

procesor"ow, gdzie  $. P_{k} (n) = n^{1 + ϵ_{k}}$

Rozwiazanie

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

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

@@ Linia 1: / Linia 1: @@
-Zadanie 1
+Zadanie ?
-Uzasadnić dlaczego algorytm  $A_{k+1}$ liczenia minimum dzia"la w czasie $O(1)$ używając  $P_{k+1}(n))$ procesor"ow,
+Uzasadnić dlaczego algorytm  $A_{k+1}$ liczenia minimum dzia"la w czasie $O(1)$ używając  <math> P_{k+1}(n))</math>
-gdzie <math> .
+ procesor"ow, gdzie <math> .P_k(n)= n^{1+\epsilon_k} </math>
-Uzasadnienie pozostawiamy jako "cwiczenie.P_k(n)= n^{1+\epsilon_k} </math>
-Rozwi"azanie
+Rozwiazanie
 <math> \max\{(\frac{n}{n^{\alpha}})^{1+\epsilon_k},\  \frac{n}{n^{\alpha}}
 \times (n^{\alpha})^{1+\epsilon_k}\}\ =\ O(P_{k+1}(n)) </math>
-gdzie $\alpha=\frac{1}{2^{k}+1}$
+gdzie <math> \alpha=\frac{1}{2^{k}+1} </math>