途中での O(1) 挿入と O(1) ルックアップの両方をサポートするリスト データ構造を設計することは不可能であることは、誰もが知っています (または知っておく必要があります)。
たとえば、リンクされたリストは O(1) 挿入をサポートしますが、ルックアップには O(N) をサポートしますが、配列はルックアップに O(1) をサポートしますが、挿入には O(N) をサポートします (最初に挿入するために償却された O(1)、最後、またはその両方)。
ただし、O(1) 挿入を次のように交換したいとします。
- 償却 O(1) 挿入
- O(log(N)) 挿入
では、これらの各ケースでのルックアップの理論的な限界は何ですか? 既存のデータ構造を知っていますか? メモリの複雑さはどうですか?