algorithm - 如何在 O(nh) 和 O(nlog(h)) 复杂度中找到帕累托最优点？

Question

任何人都可以建议一种算法来找到帕累托最优点（形成一个楼梯），就像图中给出的O(n*h)时间O(n*log(h))复杂度一样，h帕累托最优点的数量在哪里？

我使用礼品包装算法来解决这个问题（在 中O(n*h)），但它只找到凸包类型的楼梯，而错过了那些形成凹角的点。

Answer 1

将建议放在一处。

想法是使用分而治之的策略。如果我们可以在 O(n) 中找到将其余的帕累托点分成两半的帕累托点 P，那么它可以在 O(n log(h)) 中完成。这可以通过在 P 的右侧、P 的左侧和上方、P 的左侧和下方三个部分拆分点来检查。第三组没有帕累托点。并递归地对其他两组点执行相同的程序。设置三个部分的分割点比例：a, b, 1 - a - b。具有这种复杂性的是：

T(n, h) = T(a*n, h/2) + T(b*n, h/2) + O(n)
       <= T(n, h/2) + O(n)
       <= T(n, h/4) + 2 * O(n)
       <= T(n, h/8) + 3 * O(n)
       <= ...
       <= O(n log(h))

问题是在 <= O(n) 中找到具有该特征的帕累托点。一些简单的启发式算法，例如 P 其中 x >= (min(x) + max(x)) / 2，可能会产生非常好的平均值。

我不确定，但我认为可以使用k 阶统计量来找到具有该特征的点。类似于在快速排序中找到中值作为枢轴。