如何在 O(nh) 和 O(nlog(h)) 复杂度中找到帕累托最优点？
How do I find the Pareto-optimal points in O(nh) and O(nlog(h)) complexity?
任何人都可以建议一种算法来找到帕累托最优点（形成阶梯），就像在 O(n*h) 和 O(n*log(h)) 时间复杂度中的图表中给出的那样，其中 h 是帕累托最优点数？
我用礼品包装算法解决了这个问题（在O(n*h)），但它只找到凸包类型的楼梯而错过了那些形成凹角的点。
将建议放在一处。
思路是采用分而治之的策略。如果我们能在 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 to find point with that characteristic. Similar to finding median as pivot in quicksort。
任何人都可以建议一种算法来找到帕累托最优点（形成阶梯），就像在 O(n*h) 和 O(n*log(h)) 时间复杂度中的图表中给出的那样，其中 h 是帕累托最优点数？
我用礼品包装算法解决了这个问题（在O(n*h)），但它只找到凸包类型的楼梯而错过了那些形成凹角的点。
将建议放在一处。
思路是采用分而治之的策略。如果我们能在 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 to find point with that characteristic. Similar to finding median as pivot in quicksort。