15

私は部分的に順序付けられたセット、たとえば を持っていますA = [x1, x2, ...]。つまり、セット内の各xiおよびについてxj、(正確に) 4 つの可能性のうちの 1 つが真です: xi < xj、xi == xj、、xi > xjまたはは比類のないものです。xixj

xi最大の要素 (つまり、 の要素がない要素)xjを見つけたいと考えていますxi < xj。これを行うための効率的なアルゴリズムは何ですか (比較の数を最小限に抑えます)? DAG を構築してトポロジカル ソートを実行しようとしましたが、グラフを構築するだけでも O(n^2) の比較が必要であり、これは多すぎます。

私はこれを Python で行っていますが、それがわからない場合は、他の言語または疑似コードを読むことができます。

4

4 に答える 4

2

x iと x j、 i != jの間の 1 つを除いて、すべて (n は 2 を選択) の比較を見たとします。一部のシナリオでは、最大になるための唯一の 2 つの候補は、まさにこの 2 つ x iと x jです。

x iと x jを比較しないと、それらが両方とも最大であるか、どちらか一方のみが最大であるかどうかを明確に判断できません。

したがって、すべての可能な (n choose 2) (O(n 2 )) 比較をチェックする必要があります。

これは、部分的に順序付けられたセットが、比較を行うブラック ボックスで指定されていることを前提としていることに注意してください。部分的に順序付けられた集合が最初にグラフとして与えられた場合、その後サブ O(n 2 ) 時間で最大要素の集合を見つけることができます。

于 2014-02-04T19:08:54.227 に答える