1

n 対の点が与えられたとき、正の勾配を持つ線をすばやく形成できる点の対の数をどのように取得できますか?

次に n 行あり、i 番目の行には i 番目の点の x 座標と y 座標を指定する 2 つの整数 xi と yi が含まれます。同じ x 座標を持つ 2 つのポイントはなく、同じ y 座標を持つ 2 つのポイントはありません。

私の考えは、最初に x を並べ替えてから、各ポイントをその下の他のポイントと比較することです。しかし、それはまだO(n^2)です

4

2 に答える 2

4

ポイントを選択し (ランダムが最も簡単で、期待される実行時間が適切ですが、線形時間で決定論的に中央値を見つけることができます)、軸を 4 つの象限に分割します。

  x        |
           |   x   x
     x     |  x
-----------x-----------
  x        |
   x       |      x
           | x

左上から反時計回りに象限を 、 、 、IでII表しIIIますIV。

II  | I
----|----
III | IV

軸上にあるポイントは無視します (理論上の確率が 0 で、実際には簡単に処理できるエッジ ケース)。

象限内のすべての点は、 内のすべての点を持つ正の勾配の線を形成することに注意しIIIてください。IIIIV

NumPSLines(G) = |I|*|III| +
                NumPSLines(I U II) +
                NumPSLines(II U III) +
                NumPSLines(III U IV)

ここでUはユニオンを示します。

予想される値 と象限への分割が線形であると仮定すると (証明は読者に任せます)、予想される実行時間は次のようになります。E(|I|) = ... E(|IV|) = |G|/4 = n/4

T(n) = O(n) + 3T(n/2)
     = O(n) + ... + 3^k * t(n/2^k) // where k = log2(n)
     = O( log2(n) * 3^log2(n) )
     = O(n^(log2(3)) * logn)
     ~ O(n^1.6 * logn)

その境界がきついかどうかはわかりません。あまり考えていません。

このソリューションは、開始点ですが、非常に最適化できます。

于 2012-04-28T15:16:21.647 に答える
3

x で降順に並べ替え、y の反転の数を数えます。どちらのステップも O(n log n) です。

説明: 正の勾配を持つ (順序付けられていない) ペアの数は、xi > xj および yi > yj となるペア {(xi, yi), (xj, yj)} の数です。x で降順に並べ替える場合、i < j の場合に限り、xi > xj となるようにします。ys の反転の定義は、yi > yj となる i < j のペアです。

反転の数をすばやく数えます。

于 2012-04-28T15:29:32.447 に答える