所以,如果给定两个点 A(x1,y1) 和 B(x2,y2),如果 x1 <= x2 和 y1<= y2,那么我们说 B 支配 A。现在,给定很多点,我希望找出所有非支配点。简单的方法是将每个点与其他点进行比较并获得所有非支配点。但它是 O(n^2)。所以我尝试了分而治之,非常简单,我可以在 O(nlogn) 中找到它。我们的教授说,它仍然可以在 O(n) 内完成。我觉得这真的不可能。我不是要你为我解决这个问题,而是想知道是否有任何“明显”的方式可以确定在任何条件下都不能在 O(n) 中完成?但是,如果确实有可能,请不要回答,也许可以提供一些线索。
问问题
3854 次