12

n 2ラインを定義する異なる点のP={p 1 ,...,p n }が与えられた場合、最悪の場合の時間計算量で最小の勾配 (最小の絶対値) を持つラインを見つけるアルゴリズムを記述します。O(n*log(n))

4

2 に答える 2

6

定理：

  • 点の集合 P が与えられます。
  • P の 2 つの点 A と C を選択して、線 AC の絶対勾配が最小になるようにします (問題で定義されているように)。
  • 複数のポイントのペアが同じ勾配を持つ退化したケースでは、AC をその勾配を持つ最短の線分とします。
  • 次に、A と C の間に Y 座標を持つ P 内の他の点は存在しません。

証明 (矛盾による):

  • Y 座標が A と C の間にある点 B が少なくとも 1 つあるとします。
  • その場合、次の 3 つのケースが考えられます。
    • B は A および C と同一線上にあります。この場合、直線 AB または BC は AC と同じ勾配を持ちますが、どちらも AC よりも短くなります。矛盾。
    • B は、AC の「上の」半平面に落ちます。この場合、直線 AB は AC よりも傾きが浅くなります。矛盾。
    • B は、AC の「下」の半平面に落ちます。この場合、線 BC は AC よりも傾きが浅くなります。矛盾。
  • すべてのケースで矛盾が生じるため、A と C の間に点は発生しません。
  • QED。

この定理を使用すると、@Zshazz のアルゴリズムを明確に使用して正しいペアを見つけることができますO(n*log n)。

于 2012-08-30T05:39:44.070 に答える
5

y 位置に基づいてポイントを並べ替えます (任意の数のよく知られているアルゴリズムを使用して、n log n 回)。リストを 0 から n - 1 まで順番に調べ、各ポイント ペアの勾配を、これまでで最も低い勾配であることがわかったものと比較します。（それはn回です）。

全体として、それは O(n log n) になります。

擬似コード:

Let P be the list of points (this list starts at 1)
n = P.length
S = quicksort("a.y < b.y", P) // or some other O(n log n) algorithm
bestSlope = float.inf
let p1 and p2 be points
for i = 1 to n-1:
    currSlope = abs((P[i].y - P[i+1].y) / (P[i].x - P[i+1].x))
    if currSlope < bestSlope:
        bestSlope = currSlope
        p1 = P[i]
        p2 = P[i+1]
于 2012-08-30T01:17:34.790 に答える