寻找非支配对的算法

Question

给定一对整数 (a1,b1),...,(an,bn) .一对 i被一对“支配”j如果ai < aj和 bi < bj .什么是快速确定不被任何其他对支配的对列表的算法？

我们可以检查所有对，并且对于每一对，通过再次遍历所有对来检查它是否被任何其他对支配。这个算法是命令n^2 .有没有顺序算法n或 n log n ？

Answer 1

我们可以在 O(n log n) 时间内找到非支配对。

按 a_i 的降序对这些对进行排序，然后迭代这些对。另外，保持跟踪目前看到的最大 b 值，b_max。在每一步，如果下一个(a_i,b_i)pair 的 b 值大于 b_max，将其附加到答案列表并更新 b_max。最终的答案列表将是非支配对。

正确性:当且仅当某对具有更大的a时，一对才占优值和更大的 b。当我们考虑一对时，我们正在精确地比较它的 b 值到具有较大 a 的对中的最大 b 值，因此我们将一对添加到列表中当且仅当它不被支配时。

运行时:按值对对进行排序需要 O(n log n) 时间。迭代花费 O(n) 时间，因此整体运行时间为 O(n log n)。