„Algoritmuselmélet - Vizsga, 2013.05.30.” változatai közötti eltérés
| 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> | ||