Algoritmuselmélet - PZH, 2013.04.24.

2013.04.24. PZH megoldásai

1. Feladat (Van megoldás)

Egy algoritmus lépésszámáról tudjuk, hogy $T(n)=T\left(\lfloor \frac{n}{4}\rfloor \right)+O(n^2)$ és tudjuk azt is, hogy $T(1)=T(2)=T(3)=1$. Bizonyítsa be, hogy $T(n)=O(n^2)$.

Megoldás

$T(n)=T\left(\lfloor \frac{n}{4}\rfloor \right)+O(n^2)=T\left(\lfloor \frac{n}{16}\rfloor \right)+O\left(\frac{n^2}{4}\right)+O(n^2)=...=1+O(n^2)*\left(\sum _{i=0}^{\lfloor lo{g}_{4}n\rfloor }{\left(\frac{1}{4}\right)}^i\right)$
Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van képletünk:
$\sum _{i=0}^k{r}^i=\frac{1-r^{k+1}}{1-r}$ ahol $k=\lfloor lo{g}_{4}n\rfloor ,r=0.25$, vagyis $\frac{1-0.25^{\lfloor lo{g}_{4}n\rfloor +1}}{1-0.25}$
$\underset{n\to \mathrm{\infty }}{\lim }\frac{1-0.25^{\lfloor lo{g}_{4}n\rfloor +1}}{1-0.25}=\frac{1}{0.75}$

Tehát $T(n)=...=1+\frac{1}{0.75}O(n^2)=O(n^2)$

2. Feladat

TODO

Megoldás

TODO

3. Feladat

TODO

Megoldás

TODO

4. Feladat

TODO

Megoldás

TODO

5. Feladat

TODO

Megoldás

TODO

6. Feladat

TODO

Megoldás

TODO

7. Feladat

TODO

Megoldás

TODO

8. Feladat

TODO

Megoldás

TODO