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

问题描述

任何人都可以提出一种算法来找到帕累托最优点(以形成楼梯)，就像 O(n*h) 和 O(n*log(h) 中的图表中给出的那样)) 时间复杂度，其中h 是帕累托最优点的个数?

Can anybody suggest an algorithm to find Pareto-optimal points (to form a staircase) just as given in diagram in O(n*h) and O(n*log(h)) time complexity, where h is the number of Pareto-optimal points?

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

I used gift wrapping algorithm to solve this (in O(n*h)), but it only finds convex hulls type of staircase and misses those points who form concave angles.

推荐答案

把建议放在一个地方.

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

Idea is to use divide and conquer strategy. If we can find pareto point P which splits rest of pareto points in half's in O(n) than it can be done in O(n log(h)). That can be checked by splitting points in three parts right of P, left and up of P, left and down of P. Third set doesn't have pareto points. And recursively do same procedure on other two set of points. Set that three parts split points in ratio: a, b, 1 - a - b. With that complexity is:

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))

问题是在 = (min(x) + max(x))/2，可能会得到很好的平均值.

Problem is finding pareto point with that characteristic in <= O(n). Some simple heuristic like P where x >= (min(x) + max(x)) / 2, probably makes very good average.

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

I am not sure, but I think it is possible to use k-th order statistic to find point with that characteristic. Similar to finding median as pivot in quicksort.

这篇关于如何在 O(nh) 和 O(nlog(h)) 复杂度中找到帕累托最优点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！