2016-05-31 8 views
2

Ich habe ein Problem mit einer Frage in einem Papier, das mir ausgehändigt wurde und ich hoffe, dass mir jemand helfen kann. Die Frage ist:Suchmethoden Datenstrukturen

a) Das kleine Buch der Vögel mit 100 Stichwörtern und das große Buch der Vögel mit 1000 Stichwörtern ist in einer durchsuchbaren Computerform gespeichert. Es dauert ungefähr 50% so lange Zeit, um durch das große Vogelbuch als das kleine Vogelbuch zu suchen. Welche Suchmethode wird verwendet?

b) Jetzt wird die Speicher- und Suchmethode ausgetauscht. Jetzt benötigt es die gleiche Zeit, um beide Bücher zu durchsuchen. Welches ist die neue Suchmethode?

Also die erste Frage ist von Komplexität O (log (n)) und ich kenne keine Suchmethode mit dieser Zeit Komplexität. Die zweite sollte von der Ordnung O (1) sein, da sie die gleiche Zeit benötigen ??

Antwort

1

Binary search hat asymptotische Komplexität O(log n). Wenn angenommen wird, dass die Länge der Stichwörter konstant ist, kann ein hash-based Algorithmus Elemente in konstanter Zeit abrufen, siehe z.B. hash tables.