Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
| Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung | ||
| gf_informatik:daten:processing:dictionaries [2023-06-10 20:25] – hof | gf_informatik:daten:processing:dictionaries [2024-06-10 12:30] (aktuell) – hof | ||
|---|---|---|---|
| Zeile 6: | Zeile 6: | ||
| Wie wir wissen, können wir in einem (sortierten) Wörterbuch (Diktionär) effizient suchen: | Wie wir wissen, können wir in einem (sortierten) Wörterbuch (Diktionär) effizient suchen: | ||
| - | * Der Suchbereich wird fortlaufend halbiert (s.a. Binäre Suche in [[gf_informatik: | + | * Der Suchbereich wird fortlaufend halbiert (s.a. Binäre Suche in [[gf_informatik: |
| * Bei $n$ Einträgen benötigt die Suche nach einem Element nur $log_2(n)$ Zugriffe, also | * Bei $n$ Einträgen benötigt die Suche nach einem Element nur $log_2(n)$ Zugriffe, also | ||
| * $10$ Zugriffe für $1024$ Elemente, | * $10$ Zugriffe für $1024$ Elemente, | ||
| Zeile 108: | Zeile 108: | ||
| * Ein Ortsnamen kann mehrere Postleitzahlen haben - wir möchten immer die kleinste behalten (also `1000` für Lausanne, nicht `1005`). | * Ein Ortsnamen kann mehrere Postleitzahlen haben - wir möchten immer die kleinste behalten (also `1000` für Lausanne, nicht `1005`). | ||
| - | < | + | < |
| ++++Code| | ++++Code| | ||
| <code python> | <code python> | ||
| Zeile 138: | Zeile 138: | ||
| ++++ | ++++ | ||
| - | < | + | < |
| ++++Lösung: | ++++Lösung: | ||
| <code python> | <code python> | ||
hof