償却されたログ (n) のルックアップと挿入をサポートする単純なデータ構造が存在するかどうか疑問に思っていました。（要素の削除はあまり気にしません）。
私が持っていた 1 つのアイデアは、2 つの連続したブロックに分割された 1 つの連続したメモリ ブロックにすべてを格納することでした。すべての要素が並べ替えられている S 部分と、並べ替えられていない U 部分です。
挿入を実行するには、要素を U に追加します。U のサイズが log(S のサイズ) を超える場合は、連続する配列全体を並べ替えます (S と U の両方を 1 つの連続する配列として扱います)。 sort すべてが S にあり、U は空です。
ルックアップを実行するには、S で二分探索を実行し、U のすべてを調べるだけです。
ただし、アルゴリズムの償却挿入時間を計算するのに問題があります。
最終的には、必要なプロパティを備えた合理的に単純なアルゴリズム/データ構造と、償却された時間で合理的に高速に実行されることを保証するものに感謝します。
ありがとうございました！
一定量のメモリ オーバーヘッドによって、データ構造に格納された要素Nのスペース消費量がツリーには要素が含まれており、このプロパティがあります。O(N)nn > 1
これは、Nノードを持つツリー グラフにはN - 1エッジがあるという事実から導き出されます。
一定量のメモリ オーバーヘッドによって、N要素のスペース消費量が である必要があることを意味する場合N + O(1)、バランス ツリーもハッシュ テーブルもこのプロパティを持ちません。どちらもk * Nメモリを使用します。k > 1ツリーとハッシュ テーブルの場合の負荷率。
あなたのアプローチは興味深いと思いますが、U のみを並べ替えて、2 つのセットを線形時間でマージしてもうまくいかないと思います。O(logN * log(logN))更新のたびにソート (操作)を実行logNし、続いてO(n)S と U をマージする必要があります (これまでのところ、線形時間で、つまり余分な配列なしでこれを行う方法を実際に知っている人は誰もいないことに注意してください)。
償却された挿入時間は になりますO(n / logN)。O(√n)ただし、U のサイズが S の平方根に達することを許可する場合、アプローチを使用して、に近い何かを達成できる可能性があります。
どんなハッシュテーブルもそれを行います。それに関する唯一のトリッキーな部分は、競合を解決する方法です。それを行う方法はほとんどありません。他のトリッキーな部分は、正しいハッシュ計算です。