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 左侧和下方三个部分来检查。第三组没有 pareto 点。并递归地对其他两组点执行相同的过程。设置三部分按比例分割点: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) 中找到具有该特征的 pareto 点。一些简单的启发式算法，例如 P where x >= (min(x) + max(x))/2，可能会得到很好的平均值。

我不确定，但我认为可以使用 k-th order statistic找到具有该特征的点。类似于 finding median as pivot in quicksort .