Informatiker Board | Theoretische Informatik | Hashing / Lastfaktor

Informatiker Board » Themengebiete » Theoretische Informatik » Hashing / Lastfaktor » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 5 Beiträge

Shizmo

Achso ja, weil ich im Solver mit x flexibler war großes Grinsen

Ok danke!
LG

eulerscheZahl

Sieht richtig aus (die Formeln glaube ich dir einfach).
Nur das $[latex]\alpha[/latex]$ heißt plötzlich [latex]x[/latex]

Shizmo

Okay vielen Dank für deine Antwort, aber die Aufgabe hab ich nicht falsch verstanden oder?

eulerscheZahl

Die Gleichung hat keine analytische Lösung. Siehe wikipedia.
Du kannst die Seiten voneinander anziehen und dann z.B. mit Newton eine Nullstelle suchen.

Shizmo

Hashing / Lastfaktor

Hallo, ich hab mal eine Frage, die Aufgabe lautet:

Zitat:

Fuer welchen Wert des Lastfaktors $[latex]\alpha[/latex]$ ist die erwartete Anzahl von Tests bei erfolgloser Suche doppelt so groß wie die erwartete Anzahl von Tests bei erfolgreicher Suche? Es wird Hashing mit offener Adressierung zu Kollisionsvermeidung betrachtet.

Dann hab ich in meinen Unterlagen, dass die erwartete Anzahl von Tests bei erfolgloser Suche: $[latex]\frac{1}{1-\alpha}[/latex]$ ist.

Und bei erfolgreicher Suche (höchstens): $[latex]\frac{1}{\alpha}\cdot ln(\frac{1}{1-\alpha})[/latex]$ ist.

Ok, dann hab ich mir gedacht ich stelle eine Gleichung auf und löse nach alpha auf:

$[latex]2\cdot \frac{1}{\alpha}\cdot ln (\frac{1}{1-\alpha}) = \frac{1}{1-\alpha}[/latex]$

Hab dann auch ein bisschen umgeformt, aber da kommt man nicht all zu weit (bzw. ich nicht), habs dann in WolframAlpha reingeschmissen und hab auch ein Ergebnis bekommen: [latex]x = 0.715331862959162...[/latex]

.

Setz ich es ein, scheint es auch in etwa zu stimmen.
Aber irgendwie gefällt mir das ganze nicht, hab ich irgendwo einen Denkfehler? Oder kann man das irgendwie selber umformen oder abschätzen oder sonst was?

Freu mich auf jeden Tipp.
LG