3

したがって、2 つの点 A(x1,y1) と B(x2,y2) が与えられ、x1 <= x2 かつ y1<= y2 の場合、B が A を支配していると言えます。すべての非支配点を見つけます。自明なアプローチは、すべてのポイントを他のポイントと比較し、すべての非支配ポイントを取得することです。しかし、それは O(n^2) です。だから私は分割統治を試みました。かなり簡単で、O(nlogn)でそれを見つけることができます。私たちの教授は、それはまだ O(n) で実行できると言っています。本当にありえないことだと思います。私のためにこれを解決するように頼んでいるわけではありませんが、どのような条件下でも O(n) で実行できないことを確認できる「明白な」方法があるかどうか知りたいですか? ただし、本当に可能である場合は、答えないでください。

4

1 に答える 1

2

ポイントが座標の 1 つ (たとえば x 座標) で既に並べ替えられている場合、これは次のように O(n) で実行できます。

  • 最大の x 座標からポイントを処理します。
    • それらを調べながら、最大の y 座標を追跡します。
    • 現在のポイントの y 座標がこれまでの最大の y 座標よりも小さい場合は、別のポイントによって支配されています。それ以外の場合は支配的ではないため、出力に追加します。

ポイントがまだソートされていない場合、O(n) ソリューションはないと思います (ただし、様子を見ることができると思います)。

于 2013-09-27T21:29:46.997 に答える