0

何千ものキーとスコアを持つ 4 つの並べ替えられたセットがあるとします。それらは並べ替えられたセットであるため、上位のアイテムを取得することは、対数時間の複雑さで行うことができます。

簡単な方法は、セットの結合を取得してから、最上位の項目を取得することです。ただし、そうすることは、少なくともすべてのセットのすべてのアイテムの合計に対して線形です。

私が考えることができる最良の方法はこれです：

  1. すべてのセットから上位 N 個のアイテムを取得する
  2. ランクが最も低く、そのランクのスコアが最も高いアイテムを見つけます。
  3. その点数をセット数で割ります。(これよりスコアが低いキーは上位 N に入ることはありません)
  4. それらのキーの結合を取ります。(スコアは無視)
  5. すべてのセットのすべてのキーのスコアを見つけます。(キーは、あるセットではスコア 1 で、別のセットでは 10000 である場合があります)

それは、一番上のリストにある可能性のあるすべてのキーを見つけて、それらのキーで結合を行うようなものです。考慮すべき項目の数を制限するには、おそらくもっと効率的な方法があります。

[編集] キーは 1 つまたは複数のセットで発生し、それらの合計スコアによって最終的なスコアが決まります。したがって、スコアが低いすべてのセットに含まれるキーは、1 つのセットのみに含まれるスコアが高いキーよりもスコアが高くなる可能性があります。

4

1 に答える 1

3

あなたが提案するアルゴリズムはかなりぎこちないようです。次のいずれかを実行してください。

簡単な方法

for i = 1 to n
    loop through all sets and look at their smallest element,
    pick the smallest element and remove it from the sets

複雑さ: O(n * s) ここで、n は必要な項目の数、s はセットの数です。

もちろん、セットから要素を削除することが許可されていない場合は、iterators各セットに保持して、セットを変更することなく、並べ替えられた順序で要素を取得することもできます。

より効率的な方法

各セットのすべての最小要素に対して優先キューを維持します。その優先キューから最小の要素を削除するときはいつでも、e元のセットから次の要素を再挿入しますe。

O(log n)複雑さ: 「挿入」とO(log n)「最小要素の削除」の複雑さを持つ単純な優先度キューを想定します。フィボナッチ ヒープのような優れたものもありますが、これは問題なく機能します。次に、次のようになります。

  • s開始時に優先キューを満たすための挿入なので、O(s log s).
  • n「最小要素を削除する」+新しい要素を挿入するので、 （キューO(n log s)には常に要素があるため）s

したがって、どちらがはるかに優れているかを達成O(s log s + n log s)します。

比較

が非常に小さい限りs、アルゴリズム間に大きな違いはないはずであり、単純なものを選択することもできます。セット数が多い場合は、間違いなく 2 番目の方法を使用する必要があります。

ルックアップの複雑さ

私の分析では、対数ルックアップ係数を省略して各セットの最小要素を見つけ、各セットの最小要素はO(1)並べ替えられたリストのように で取得できると仮定しました。ルックアップ コストを からO(1)にO(log n)変更しても、アルゴリズムを変更しない追加の要素が導入されるだけです。O(log n)さらに、通常は最初のルックアップで一度だけ支払います。その後、通常、最小要素への反復子があります。その後、反復子を使用してさらに各要素にアクセスするだけO(1)です。

于 2014-06-10T10:31:02.607 に答える