„Algoritmuselmélet - PZH, 2013.04.24.” változatai közötti eltérés
(Új oldal, tartalma: „==2013.04.24. PZH megoldásai== ===1. Feladat=== TODO {{Rejtett |mutatott=<big>'''Megoldás'''</big> |szöveg= TODO }} ===2. Feladat=== TODO {{Rejtett |mutatott=<big>…”) |
|||
| 1. sor: | 1. sor: | ||
==2013.04.24. PZH megoldásai== | ==2013.04.24. PZH megoldásai== | ||
| − | ===1. Feladat=== | + | ===1. Feladat (Van megoldás)=== |
| − | + | Egy algoritmus lépésszámáról tudjuk, hogy <math> T(n) = T\left(\left \lfloor \frac{n}{4} \right \rfloor\right) + O(n^2)</math> és tudjuk azt is, hogy <math> T(1)=T(2)=T(3)=1</math>. Bizonyítsa be, hogy <math> T(n)=O(n^2)</math>. | |
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
| − | + | <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> | ||
| + | <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> \lim_{n \to \infty}\frac{1-0.25^{\left \lfloor log_4n \right \rfloor+1}} {1-0.25} = \frac{1}{0.75}</math><br> | ||
| + | Tehát <math> T(n)=...=1+\frac{1}{0.75}O(n^2)=O(n^2)</math> | ||
}} | }} | ||
A lap 2013. június 10., 20:54-kori változata
Tartalomjegyzék
2013.04.24. PZH megoldásai
1. Feladat (Van megoldás)
Egy algoritmus lépésszámáról tudjuk, hogy [math] T(n) = T\left(\left \lfloor \frac{n}{4} \right \rfloor\right) + O(n^2)[/math] és tudjuk azt is, hogy [math] T(1)=T(2)=T(3)=1[/math]. Bizonyítsa be, hogy [math] T(n)=O(n^2)[/math].
[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]
Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van képletünk:
[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]
[math] \lim_{n \to \infty}\frac{1-0.25^{\left \lfloor log_4n \right \rfloor+1}} {1-0.25} = \frac{1}{0.75}[/math]
2. Feladat
TODO
3. Feladat
TODO
4. Feladat
TODO
5. Feladat
TODO
6. Feladat
TODO
7. Feladat
TODO
8. Feladat
TODO
