algorithm - 寻找 f(x) = a*min(b, x) 形式的函数最大值的算法？

Question

(a, b)我有一个带有 a > 0and的元组数组b > 0。
每个元组代表一个函数f，使得f(x, a, b) = a * min(b, x).

是否有已知的算法x来查找哪个元组返回最大值？
我不想评估每个函数来检查最大值，因为我会针对不同的x.

例子：

array = [ (1, 10), (2, 3) ]
x < 6 -> choose (2, 3)
x = 6 (intersection point) -> either (1, 10) or (2, 3) doesn't matter
x > 6 -> choose (1, 10)

所以问题是这些元组可以按a或按 排序b。但是它们之间可能有很多交叉点（如果我们将它们可视化为图形）。所以我想避免任何 O(n^2) 排序算法来检查某些范围x是最好的函数。我的意思是我不想将每个函数与所有其他函数进行比较，以找到从哪个点x'（交点）开始，我应该选择一个而不是另一个。

标签： algorithmsortingoptimizationconvex-hullconvex-optimization

Answer 1

假设a' bs 和 queried x's 总是非负数，每个查询都可以在预处理步骤O(log(n))后及时完成：O(n*log(n))

预处理步骤消除了严格受他人支配的此类功能。例如，(5, 10)大于(1, 1)每个 x。（因此，如果(5, 10)数组中有，那么我们可以删除(1, 1)，因为它永远不会是任何 x 的最大值。）

这是一般条件：当且仅当和时，函数(a, b)大于每个 x 。（这很容易证明。）(c, d)c > a(c*d > a*b)

现在，我们要做的是删除(a, b)存在(c, d)这样c > a和的函数(c*d > a*b)。这可以在 O(n*log(n)) 时间内完成：

1 - 按字典顺序对元组进行排序。我的意思是按字典顺序首先比较它们的第一个坐标，如果它们相等，然后比较第二个坐标。例如，排序后的数组可能如下所示：

(1, 5)
(1, 17)
(2, 9)
(4, 3)
(4, 4)

2 - 以相反的顺序遍历已排序的数组，并跟踪a*b您迄今为止遇到的最大值。我们称这个值M。现在，假设我们在循环中处理的元素是(a, b). 如果a*b < M，我们删除这个元素。因为对于(c, d)我们之前处理过的一些东西，c > a和c*d > a*b， 和 ， 因此(a, b)都是无用的。在这一步之后，示例数组将变为：

(2, 9)
(4, 4)

(4, 3)被删除了，因为它被(4, 4). (1, 17)并被(1, 5)删除，因为它们由(2, 9).

一旦我们去掉了所有对于任何 x 都不是最大值的函数，剩下的函数的图形将如下所示。

如图所示，从与前一个函数相交的点到与后一个函数相交的点，每个函数都是最大值。对于上面的示例，(4, 4)相交(2, 9)于x = 8。(4, 4)直到 的最大值也是如此x = 8，在那之后(2, 9)是最大值。我们想要计算数组中连续函数相交的点，这样对于给定的 x，我们可以对这些点进行二分搜索以找到哪个函数返回最大值。