11. gyakorlat
Hasítás
Jelölések
- \(m\): méret
- \(T(0\dots m)\)
- \(T[0], T[1], \dots,T[m-1]\)
- \(\varnothing\)
- \(E\)
- \(D\)
- \(n\)
- \(\alpha\)
- \(U\)
- \(h:U \rightarrow 0\dots (m-1)\)
Sikeres beszúrás ill. sikertelen keresés várható hossza:
\[
\dfrac{1}{1-\alpha}
\]
Sikeres keresés illetve sikertelen beszúrás várható hossza:
\[
\dfrac{1}{\alpha}\ln\dfrac{1}{1-\alpha}
\]
Fontos! Ezt Ásványi szereti kérdezni vizsgában.