私はこれをアルゴリズムファイナルの最後の質問として持っていました(現在完了しています):
(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 つの頂点間に有向パスがあるかどうかの一定時間のルックアップが与えられた任意の有向ツリーの葉を見つけます。