„Anal2-magic” változatai közötti eltérés
Nincs szerkesztési összefoglaló |
Nincs szerkesztési összefoglaló |
||
| 208. sor: | 208. sor: | ||
Ezekhez ajanlott megnezni par feladatot, es azon ertelmezni :D<br /> | Ezekhez ajanlott megnezni par feladatot, es azon ertelmezni :D<br /> | ||
<br /> | <br /> | ||
== Linearis rekurzio == | |||
(ez nagyon magic)<br /> | |||
megoldas alakja: f(n) = q<sup>n</sup> // q != 0<br /> | |||
'''pelda:'''<br /> | |||
f(n) = 4 * f * (n - 1) - 3 * f * (n - 2)<br /> | |||
ebbol:<br /> | |||
q<sup>n</sup> = 4 * q<sup>n - 1</sup> - 3 * q<sup>n - 2</sup><br /> | |||
a legalacsonyabb hatvanyu q-val osztunk.<br /> | |||
q<sup>2</sup> = 4 * q - 3 --> masodfoku<br /> | |||
q<sub>1</sub> = 1<br /> | |||
q<sub>2</sub> = 3<br /> | |||
f(n) = C1 + C2 * 3<sup>n</sup><br /> | |||
Ha O(1) tipusu megoldasok kellenek:<br /> | |||
f(n) = O(1): JK, hogy |f(n)| <= K * 1 n > N (veges sok kivetel)<br /> | |||
tehat: f(n)-nek korlatosnak kell lenni:<br /> | |||
C2 = 0<br /> | |||