„Algoritmuselmélet - PZH, 2013.04.24.” változatai közötti eltérés

← Régebbi szerkesztés Újabb szerkesztés →

VizuálisWikiszöveges

@@ 6. sor: / 6. sor: @@
 |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>
+<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}{16} \right) + O(n^2)=...=1 + O(n^2)\cdot\left(\sum_{i=0}^{\left \lfloor log_4n \right \rfloor} \left (\frac{1}{16}  \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>\sum_{i=0}^{k} r^i = \frac{1-r^{k+1}} {1-r} </math>, ahol <math> k = \left \lfloor log_4n \right \rfloor, r = \frac{1}{16}</math>, vagyis <math>\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}}</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>
+<math>\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}} < 2 ,</math><big>ha</big> <math> n \geq 1</math>
+Tehát <math> T(n)=...=1+2 \cdot O(n^2)=O(n^2)</math>
 }}