12. gyakorlat

Négyzetes hasítás

\[ h(k,i) = \left(h_1\left(k\right) + c_1*i + c_2*i^2\right) mod m \]

$i =(0,1,\dots,m-1) \land c_2 \ne 0$

fontos, hogy a próbasorozat az egész táblát lefedje

ha $m$ egy kettő-hatvány, akkor $c_1$ és $c_2$ is lehet $\frac12$

fontos, hogy among us

$h(k, i) = (h_1(k)+i\cdot h_2(k))\mod m$

Ahol $h_2$:

Vizsgán a táblázatot ki kell tölteni (a táblázatot megkapjuk)!

:naez:

$O(1g) = \left\{f|\exists c > 0 \land N \in \mathbb{N}: \forall n \ge N: \ge c*g(n)\right\}$

f-nek g

$\Omega(g) = \left\{f|\exists c > 0 \land N \in \mathbb{N}: \forall n \ge N: c * g(n) \le f(n)\right\}$

f-nek

$\Theta(g) = \left\{f|\exists c_1, c_2 > 0 \land N \in \mathbb{N}: \forall n \ge N: c_1 * g(n) \le f(n) \le c_2 * g(n)\right\}$

f-nek g

$\Theta(g) = O(g) ∩ \Omega(g)$
$o(g) ⊂ O(g) \ \Omega(g)$
$ω(g) ⊂ \Omega(g) \ O(g)$
ha $f \in O(g)$ ´es $g \in O(h)$, akkor $f \in O(h) $(tranzitivit´as, $\Omega$ ´es $\Theta$ eset´en is teljes¨ul)
$f \in Θ(g) ⇐⇒ g \in \Theta(f)$ (szimmetria)
$f \in O(g) ⇐⇒ g \in \Omega(f)$ (felcser´elt szimmetria)
$f \in O(f) ´es f \in \Omega(f)$ ´es $f \in Θ(f)$ (reflexivit´as)
ha f, $g \in O(h)$, akkor $f + g \in O(h)$ ($\Omega$ ´es $\Theta$ eset´en is)
$f + g \in \Theta(max{f, g})$
Ha $f \in O(h1)$ ´es $g \in O(h2)$, akkor $f ∗ g \in O(h1 ∗ h2)$

struki: egyedi feladat, fabejárás likely

máj. 28-ig jelezni, ki akar javzh-t írni