途中での O(1) 挿入と O(1) ルックアップの両方をサポートするリスト データ構造を設計することは不可能であることは、誰もが知っています (または知っておく必要があります)。
たとえば、リンクされたリストは O(1) 挿入をサポートしますが、ルックアップには O(N) をサポートしますが、配列はルックアップに O(1) をサポートしますが、挿入には O(N) をサポートします (最初に挿入するために償却された O(1)、最後、またはその両方）。
ただし、O(1) 挿入を次のように交換したいとします。
では、これらの各ケースでのルックアップの理論的な限界は何ですか? 既存のデータ構造を知っていますか? メモリの複雑さはどうですか？
ロープやフィンガーツリーのようなツリーベースのデータ構造は、多くの場合、任意の位置で対数挿入時間を提供できます。トレードオフはアクセス時間であり、指の木の端のような特別な場合を除いて対数になる傾向があります。
動的配列は、最後に償却された定数挿入を提供できますが、途中で挿入するには、配列の一部をコピーする必要があり、時間的には O(N) です。
償却定数の中間挿入をサポートするデータ構造を実装することはおそらく可能です。両端に追加する場合は、動的配列として扱います。中央に挿入する場合は、古い配列を保持し、リストの新しい「中央」を含む新しい配列を「上」に追加します。中央の左側または右側のデータには古い配列を使用します。最初の中間挿入の後、アクセス時間は対数になり、どのデータがどのレイヤーにあったかを追跡することはすぐに複雑になります。
これは、ウィキペディアの記事で言及されている「階層化された」動的配列である可能性がありますが、これ以上調査していません。
そのようなデータ構造を誰も実際に使用しない理由は、真ん中に挿入することが最も必要とされるケースはめったになく、ほとんどの現実のケースでは対数挿入 (ツリーを使用) で十分であるためだと思います。
これらはまだ未解決の問題ですが、私が知っている最良の境界は、O(sqrt(lg(n))) の挿入、削除、およびルックアップを含む Arne Andersson のSublogarithmicsearching without multiplicationsによるものです。ただし、これには 2^k の追加スペースが必要です。ここで、k はデータ構造に格納される整数のビット数です。そのため、アンダーソンのデータ構造の代わりにバランスの取れたバイナリ ツリーを引き続き使用しています。データ構造のバリアントでは O(1) ルックアップが可能ですが、追加のスペースは n2^k に増加します。ここで、n はデータ構造内の要素の数です。ランダム化されたバリアントは追加のスペースを使用しませんが、sqrt(lg(n)) 挿入/削除/検索時間は、最悪の場合の時間ではなく平均スペース時間になります。