O (1) Suche in nicht zusammenhängendem Speicher?

Ja, hier ist ein Beispiel in C ++:

Der Hauptunterschied zu std :: deque besteht darin, dass O (n) push_front anstelle von O (1) ist, und in der Tat gibt es ein kleines Problem bei der Implementierung von std :: deque, um all zu haben von:

1. O (1) push_front
2. O (1) push_back
3. O (1) op []

Vielleicht habe ich "falsch interpretiert", ohne einen zusammenhängenden Speicherblock der Größe O (N) oder größer zu verwenden, was peinlich erscheint. Können Sie erklären, was Sie wollen? Ich habe interpretiert als "keine einzige Zuweisung, die ein Element für jedes Element in der dargestellten Reihenfolge enthält", wie hilfreich wäre, um große Zuweisungen zu vermeiden. (Obwohl ich eine einfache Zuordnung der Größe N / B für den Vektor habe.)

Wenn meine Antwort nicht zu Ihrer Definition passt, wird nichts passieren, es sei denn, Sie begrenzen die maximale Größe des Containers künstlich. (Ich kann Sie auf LONG_MAX-Elemente beschränken, speichern Sie die obigen Blöcke stattdessen in einer Baumstruktur und rufen Sie zum Beispiel die O (1) -Lookup-Methode auf.)

Sie können einen trie verwenden, bei dem die Länge des Schlüssels begrenzt ist. Als Lookup in einem Trie mit einem Schlüssel der Länge m ist O(m) , wenn wir die Länge der Schlüssel gebunden haben, dann haben wir m gebunden und jetzt ist die Suche O(1) .

Denken Sie also an den a Trie, bei dem die Schlüssel Strings im Alphabet { 0, 1 } sind (d. h. wir denken an Schlüssel als binäre Repräsentation von ganzen Zahlen). Wenn wir die Länge der Schlüssel auf 32 Buchstaben begrenzen, haben wir eine Struktur, die wir als durch 32-Bit-Ganzzahlen indiziert betrachten können und die in O(1) -Zeit zufällig zugänglich ist.

Hier ist eine Implementierung in C #:

Hier ist eine Beispielverwendung:

Nun, da ich Zeit damit verbracht habe, darüber nachzudenken, und könnte argumentiert werden, dass alle Hashtabellen entweder ein zusammenhängender Block der Größe & gt; N sind oder eine Bucket-Liste proportional zu N haben, und Rogers Top-Level-Array von Block s ist O (N) mit einem Koeffizienten kleiner als 1, und ich schlug eine Korrektur in den Kommentaren zu seiner Frage vor, hier geht es:

half_power_deque implementiert das Löschen aller bis auf den letzten Block, wobei half_first_block_mag entsprechend geändert wird. Dies ermöglicht die Verwendung von O (max über Zeit N) Speicher, amortisierte O (1) -Einfügungen an beiden Enden, niemals die Ungültigkeit von Referenzen und O (1) Nachschlagen.