Bestimmen, ob eine ganze Zahl in einer Menge in O (1) erwarteter Zeit und O (logn) worst case

Question

Ich muss eine Datenstruktur beschreiben, die bestimmen kann, wo eine bestimmte ganze Zahl in einer Menge in O (1) erwartete Zeit und O (logn) worst case auch verbrauchen O (n) Raum. Ich habe mir eine Tabelle angesehen, die gängige Datenstrukturen und große Zeit/Raum-Komplexitäten enthält, aber ich kann anscheinend keine finden, die diesen Anforderungen entsprechen. Gibt es eine Möglichkeit, eine BST zu modifizieren, um diese Anforderungen zu erfüllen?

Answer 1

Wenn @Carcigenicate kommentiert wurde, zeigt eine Hashmap das von Ihnen gewünschte Verhalten an. Es hat eine konstante Lookup-Zeit O(1), außer im Falle von Kollisionen. Im Falle von Kollisionen erstellen Hashmaps typischerweise eine Liste von Elementen für einen bestimmten Bucket. Im schlimmsten Fall würde sich eine Hashmap wie eine Liste verhalten. Dies würde jedoch eine Worst-Case-Suchzeit von O(n) bedeuten, die nicht zu Ihrer Anforderung passt.

Java, in seiner neuesten 8 Version, ausgesetzt eine HashMap Klasse, die ausgewogene Bäume anstelle von Listen verwendet, um Elemente zu speichern, die mit dem gleichen Eimer kollidieren. Dies garantiert eine Worst-Case-Suchzeit von O(logn).

Also, um Ihr Problem zu lösen, müssten Sie die Implementierung einer hashmap ändern, um Bäume für Kollisionen zu verwenden. Wenn Sie Java 8 verwenden, ist das Leben bereits gut und Sie können einfach mit HashMap laufen.