小编jac*_*ven的帖子

我把它作为算法最终的最后一个问题(现已完成):

给定一组(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 …