3. Rekurzív egyenletek, Binet formula¶

Lineáris keresés¶

Készítsünk algoritmust, amely egy elemet megkeres egy adott tömbben!

Megjegyzés

Hogyan lehetne az algoritmust gyorsítani?

Binet formula¶

Mire szolgál a Binet formula, és hogyan néz ki?

\[F_n = \dfrac{1}{\sqrt{5}}\left( \Phi^n - \overline{\Phi}^n \right), \quad F_n = \text{Round} \left( \dfrac{1}{\sqrt{5}} \Phi^n \right), \quad \Phi = \dfrac{1 + \sqrt{5}}{2}, \quad \overline{\Phi} = \dfrac{1 - \sqrt{5}}{2}.\]

A Binet formula segítségével határozzuk meg a Fibonacci sorozat 37-edik, és 38-adik elemét!
A Binet formula gyorsabb számítást eredményez-e, mint az iterációs/rekurzív?
Ha igen, akkor mennyivel gyorsabb a számítási mód?

Rekurzív egyenletek¶

Legyen \(T(1) = 1\) mindegyik esetben!

\(T(n) = T(n - 1) + 2\), számtani sorozat
\(T(n) = 3T(n - 1)\), mértani sorozat
\(T(n) = 2T(n - 1) + 3\)
\(T(n) = T(n - 1) + 2n\)
\(T(n) = T\left( \dfrac{n}{2} \right) + 1\)

Mester tétel¶

Mondjuk ki a mester tételt, és határozzuk meg a növekedési rendjét az alábbi \(T\) függvényeknek!

\(T(n) = T\left( \dfrac{n}{2} \right) + 1\)
\(T(n) = 4T\left( \dfrac{n}{2} \right) + n\)
\(T(n) = 4T\left( \dfrac{n}{2} \right) + n^2\)
\(T(n) = 4T\left( \dfrac{n}{2} \right) + n^3\)
\(T(n) = 8T\left( \dfrac{n}{2} \right) + 2^n\)
\(T(n) = 3T\left( \dfrac{n}{3} \right) + n\)
\(T(n) = T\left( \left\lfloor \dfrac{2n}{3} \right\rfloor \right) + \sqrt{n}\)
\(T(n) = 25T\left( \left\lceil \dfrac{n}{5} \right\rceil \right) + \log n\)