„Algoritmuselmélet - Vizsga, 2013.05.30.” változatai közötti eltérés
A VIK Wikiből
| 42. sor: | 42. sor: | ||
|szöveg= | |szöveg= | ||
<math> T(n) = T\left(\left \lfloor \frac{n}{4} \right \rfloor\right) + O(n^2 | <math> T(n) = T\left(\left \lfloor \frac{n}{4} \right \rfloor\right) + O(n^2) = T\left(\left \lfloor \frac{n}{16} \right \rfloor\right) + O\left(\frac{n^2}{4} \right) + O(n^2)=...=1 + O(n^2)*\left(\sum_{i=0}^{\left \lfloor log_4n \right \rfloor} \left (\frac{1}{4} \right )^i\right)</math><br> | ||
Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van képletünk:<br> | Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van képletünk:<br> | ||
<math>\sum_{i=0}^{k} r^i = \frac{1-r^{k+1}} {1-r} </math> ahol <math> k = \left \lfloor log_4n \right \rfloor, r = 0.25</math>, vagyis <math>\frac{1-0.25^{\left \lfloor log_4n \right \rfloor+1}} {1-0.25}</math><br> | <math>\sum_{i=0}^{k} r^i = \frac{1-r^{k+1}} {1-r} </math> ahol <math> k = \left \lfloor log_4n \right \rfloor, r = 0.25</math>, vagyis <math>\frac{1-0.25^{\left \lfloor log_4n \right \rfloor+1}} {1-0.25}</math><br> | ||
A lap 2013. június 7., 23:18-kori változata
2013.06.06. vizsga megoldásai
1. Feladat
TODO
Megoldás
2. Feladat
TODO
Megoldás
3. Feladat
TODO
Megoldás
4. Feladat
TODO
Megoldás
5. Feladat (Van megoldás)
Egy algoritmus lépésszámáról tudjuk, hogy Értelmezés sikertelen (formai hiba): {\displaystyle T(n) = T\left(\left \lfloor \frac{n}{4} \right \rfloor\right) + Ο(n^2)} és tudjuk azt is, hogy . Bizonyítsa be, hogy .
Megoldás
6. Feladat
TODO
Megoldás
7. Feladat
TODO
Megoldás
8. Feladat
TODO
Megoldás
