9

空間効率と時間効率に優れた、2 つの型の間の有限全単射を表す関数データ構造を探しています。

たとえば、サイズ n の全単射 f を考えると、次のようになれば幸いです。

  • 新しい要素のペアで f を拡張すると、複雑さが O(ln n) になります。
  • f(x) または f^-1(x) のクエリの複雑さ O(ln n)
  • f の内部表現は、2 つの有限マップ (f とその逆を表す) を持つよりも空間効率が良い

この論文のように順列の効率的な表現を認識していますが、それは私の問題を解決していないようです。

4

2 に答える 2

11

比較的似た質問については、私の回答をご覧ください。提供されたコードは、一般的な NxM 関係を処理できますが、(二分探索木の場合と同様に) 全単射のみに特化することもできます。

完全を期すために、ここに回答を貼り付けます。

最も簡単な方法は、単方向マップのペアを使用することです。多少のコストはかかりますが、それほど良くなることはありません (専用のバイナリ ツリーを使用すると少し良くなる可能性がありますが、自分で実装する必要がある場合は、複雑なコストがかかります)。基本的に、ルックアップは同じくらい速くなりますが、追加と削除は 2 倍遅くなります。これは、対数演算にはそれほど悪くありません。この手法のもう 1 つの利点は、キーまたは値の型に特化したマップ型があれば、それを使用できることです。特定のジェネラリスト データ構造では、柔軟性があまり得られません。

別の解決策は、四分木を使用することです (NxN の関係を 1xN と Nx1 の関係のペアと見なすのではなく、タイプのデカルト積 (キー*値) の要素のセット、つまり空間しかし、時間とメモリのコストが 2 つのマップよりも優れているかどうかはわかりません。テストする必要があると思います。

于 2012-05-20T07:49:56.977 に答える
6

3 番目の要件を満たしていませんが、bimapが適しているようです。(各方向に 1 つずつ、使いやすい 2 つの有限マップを作成するだけです。)

于 2012-05-19T22:57:03.077 に答える