用于查找形式为 f(x) = a*min(b， x) 的函数最大值的算法

Question

我有一个元组数组，(a, b)a > 0和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'(交点)，并且我应该选择一个而不是另一个。

Answer 1

假设a的、b的和查询的x总是非负的，每个查询都可以在O(n*log(n))预处理步骤后的O(log(n))时间内完成：

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

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

现在，我们要做的是删除存在(c, d)的此类功能(a, b)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，我们可以对这些点进行二进制搜索以找到哪个函数返回最大值。

Answer 2

效率的关键是避免无用的工作。如果你想象一个决策树，修剪分支是一个经常用于的术语。

对于您的情况，决策基于在两个函数(或参数元组)之间进行选择。为了选择这两个函数中的任何一个，您只需确定它们为您提供相同值的值x。其中一个对于较小的值表现更好，另一个对于较大的值表现更好。另外，不要忘记这部分，可能一个功能总是比另一个功能表现得更好。在这种情况下，可以完全删除性能较差的那个(另见上文，避免无用的工作！

使用此方法，可以从此切换点映射到左侧的函数。为任意值找到最优函数只需要找到下一个更高的切换点。

顺便说一句：确保你已经进行了单元测试。这些事情很繁琐，尤其是浮点值和舍入误差，所以你要确保你可以运行一套不断增长的测试，以确保一个小的错误修复不会破坏其他地方的东西。

Answer 3

我认为您应该首先根据"b"然后根据"a"对数组进行排序。现在，对于每个 x，只需使用二叉搜索并找到 min(b，x) 根据值仅给出 b 或 x 的位置。因此，从这一点开始，如果 x 很小，那么 b 的所有即将到来的值都将元组作为 t1，您可以使用该函数计算值，对于小于 x 的 b 值，您强制需要遍历。我不确定，但这是我能想到的。

Answer 4

在对数据进行预处理后，可以在时间O(log(n))中计算这个最大值，其中n是元组(a, b)的数量。

首先，让我们看一个稍微简单的问题：你有一个(c, b)对的列表，你想找到c值最大的一个，条件是b<=x，并且你想对不同的x值做很多次。例如，以下列表：

c   b
------
11  16
8  12
2   6
7   9
6  13
4   5

使用此列表，如果您用x=10询问，c的可用值为 2、7 和 4，最大值为 7。

让我们按b对列表进行排序：

c   b
------
4   5
2   6
7   9
8  12
6  13
11  16

当然，此列表中的某些值永远无法给出答案。例如，我们永远不能在答案中使用b=2、c=6行，因为如果6<=x那么5<=x，所以我们可以使用c=4行来获得更好的答案。因此，我们不妨删除列表中类似的对，即到目前为止c值不是最高的所有对。因此，我们将列表缩减为：

c   b
------
4   5
7   9
8  12
11  16

给定此列表，在b上有一个索引，很容易找到c的最高值。您所要做的就是在列表中找到b的最高值，即<=x，然后返回相应的值c。

显然，如果您更改问题，以便只想要带有b>=x(而不是b<=x)的值，您可以做完全相同的事情。

右。那么这对你提出的问题有什么帮助呢？

对于给定的值x，您可以将问题分成 2 个问题。如果你能回答这两个问题，那么你就可以回答整个问题：

1. 在与b<=x(a, b)的对中，哪一个给出最高的f(x,a,b) = a*b值？
2. 在与b>=x(a, b)的对中，哪一个给出最高的f(x,a,b) = a*x值？

对于 (1)，只需让每对c=a*b，然后完成上面概述的整个索引严格性。

对于(2)，让c=a做上面的索引，但翻转做b>=x而不是b<=x;当你得到a的答案时，不要忘记乘以x。