5

私はこれをアルゴリズムファイナルの最後の質問として持っていました(現在完了しています):

(x,y) 点の集合 P が与えられたとき、M ( P)を P 上の次の半順序付けが与えられた最大の集合とします。

(x,y) < (x',y') if and only if x < x' and y < y'.

したがって:

M({(0,0),(1,1)})={(1,1)}
M({(0,0),(0,1),(1,0)})={(0,1),(1,0)}

M(P) を時間計算量 O(nh)、O(n log n)、O(n log h) で計算するアルゴリズムを与えてください (n = |P| および h=|M(P)|)。

私の O(nh) アルゴリズム:

Declare M as a set of points
foreach p in P:
  addP = true
  foreach m in M:
    if(p < m):
      addP = false
      break
    if(m < p):
      M.remove(m)
  if(addP)
    M.add(p) //doesn't add if M contains p
return M

私の O(n log n) アルゴリズム:

Declare M as a set of points
Sort P in reverse lexicographic order
maxY := -inf
foreach p in P:
  if(p.y > maxY):
    M.add(p)
    maxY = p.y
return M

O(n log h) アルゴリズムとは何ですか?
私の直感では、これは最初のアルゴリズムを修正したものですが、ポイントごとにスキャンする必要のない巧妙なデータ構造 (おそらくバイナリ ツリーの修正) を使用しています。

一般的なポーズセットのようなアルゴリズムはありますか?
これは、与えられた頂点のリストと、与えられた 2 つの頂点間に有向パスがあるかどうかの一定時間のルックアップが与えられた任意の有向ツリーの葉を見つけます。

4

1 に答える 1

6

これは本当に悪質な試験問題です (インストラクターが凸包の O(n log h) アルゴリズムの 1 つについて教えてくれた場合を除きます。この場合、それは単にです)。

この問題は 2D MAXIMA と呼ばれ、凸包の計算と密接な関係があるため、通常は計算幾何学の領域です。最大問題に対する O(n log h) アルゴリズムの適切な説明は見つかりませんが、Timothy Chan の 2D CONVEX HULL に対する O(n log h) アルゴリズムは、味を与えるはずです。

于 2011-12-14T15:56:31.687 に答える