3

そのため、最初から n 番目の要素を移動し、それを前に移動する必要があります (そして、0、..、n-1 項目を右にシフトします)。使用するのに最適なデータ構造は何ですか?どうすればよいですか?

私はすでにスキップリストについて考えていますが、インデックス経由でアクセスするために O(log n) を取得する方法がわかりません。使用すべきより良いもの (木など) はありますか?

前もって感謝します..

言語: C++

免責事項: はい、これは宿題です。

4

5 に答える 5

6

各ノードで、そのサブツリーに格納されているアイテムの数をキャッシュする任意のバランスの取れたバイナリ ツリー (赤黒ツリーなど) を使用できます。アイテム自体は葉に収納できます。インデックス付きルックアップでは、インデックスを左側のサブツリーのサイズと比較します。小さければそこにある。それ以外の場合は右側にあるため、インデックスから左側のサブツリーのサイズを差し引いて、右側のサブツリーに相対的なインデックスを取得します。次に、再帰します。ツリーのバランスが取れているため、これにより O(log n) が得られます。

他の操作については、赤黒木用の既存のアルゴリズムを使用できます。サイズを追跡するために、いくつかの小さな変更が必要です。たとえば、アイテムを最前面に移動するには、まず上記のアルゴリズムを使用してアイテムを見つけ、削除して最前面に再挿入します。これらの各ステップは O(log n) なので、総実行時間も O(log n) です。

于 2013-05-26T14:51:37.327 に答える
2

これらの質問は常に基本原則に基づいています。これは、コンピューター サイエンスの「フリー ランチ」と考えることができます。それは、時間と空間のトレードオフです。

何かを非常に高速に実行したい場合は、より多くのスペースを消費する必要があり、その逆も同様です。

たとえば、配列は小さなスペースに最適なケースですが、何かを移動する必要がある瞬間は恐ろしいものです。Hashtable は高速アクセスに最適なケースですが、無駄なスペースを大量に消費します。

したがって、宇宙経済と時間経済のどちらがより重要かを判断する必要があります。

この場合、インデックス付き lokup の O(log n) を探している場合は、スキップ リストまたはインデックス付きスキップ リストを使用できます。これらのデータ構造は、スペースを犠牲にして (より多くのポインタが「スキップされた」リスト)。

于 2013-05-26T14:44:05.933 に答える
0

空間の複雑さについてはわかりませんが、ポインターの配列とリンクリストを使用して、O(1) 時間で同じことを行うことができます (配列の場合に述べたように、データを前に配置する必要があります)。リンクリストノードのアドレスを同じ順序で格納する番号のリンクリストと同じサイズの配列を作成します。任意の n 番目の値について、配列から n 番目のノードと 1 番目のノードのアドレスを選択し、それらのノードの番号を置き換えます。 ...............

于 2013-05-26T14:46:16.923 に答える
0

LinkedHashMap の種類の DS を使用できると思います。Java には、 LinkedHashMapの組み込み実装があります。したがって、最後のオブジェクトを最初の位置に移動するには、最後のオブジェクトを削除してから同じ DS に追加する必要があります。検索は再び O(1) 時間で実行できます。他の言語でも、LinkedList をプライマリ DS として使用し、それに加えて HashMap DS によって拡張されて実装するのは難しいことではありません。

于 2013-05-26T14:42:21.737 に答える
0

たぶん、二重連結リストで十分です:) 二重連結リストを使用する場合:

最初から目的のインデックスまですべての要素をトラバースする必要があるため、インデックス作成には O(n) かかります。

削除操作は簡単で、O(1) しかかかりません。

先頭の目的の要素を移動する操作も O(1) かかります。

全体として、〜O（n）操作が得られます...

于 2013-05-26T14:49:57.313 に答える