algorithm - 查找最小函数

Question

好的，这是交易。我有一堆线性函数，a * x + b。

我的目标是回答以下问题/查询：x = q 处的最小函数是什么？

例如：如果我有函数 f(x) = 3*x + 2、g(x) = 5*x - 6 和 h(x) = 2*x + 1，我将回答例如：

• 对于 x = 4，函数 h

• 对于 x = 2，函数 g

• 对于 x = 1，函数 g

我的想法是这样的：

1. 按 x 的系数对函数进行降序排序。

2. 按升序对查询进行排序

3. 摆脱并行函数，保留具有最小常数项的函数（例如：如果我有 f(x) = 2*x + 4 和 g(x) = 2*x + 2，f(x) 将永远不会小于 g(x)，所以我不需要 f(x))。

4. 现在我在从-inf到某个实数的区间上，称之为w1，我知道在这个区间上，线性系数最高的函数是最小的

5. 通过找到最小的 x1 st f(x1) = g(x1) 来找到 w1，其中 f 是我当前的函数，g 以较小的线性系数遍历所有其他函数，w1 = x1

6. 只要我的查询在区间 (-inf, w1) 内就重复：输出当前函数，然后继续下一个查询。

7. 如果我仍然有需要回答的查询，让当前函数与我的实际当前函数在 x = w1 处相交，而不是 -inf put w1，重复相同的步骤。

但是，我的实现或想法还不够快。有什么我没有注意到的可以加快我的程序的吗？

先感谢您。

Answer 1

你能不能只解决它们的交点，并为域中的每个区间存储最大的函数？

编辑-详细说明，如果您要解决 x 的任何一对函数，则 x 表示这两个函数中的一个变得大于另一个的值。将会有可定义的区间，其中最小函数对于区间中的所有值都是相同的。

这是您的 3 个示例函数的图。

该图的间隔（具有相应的最小函数）将是

(-∞, 7/3]     => 5x - 6
(7/3, ∞]      => 2x + 1

现在，在运行时，您只需执行“q 属于什么区间” ，而不是"What is the minimum function at x = q " 。

而且，如果我没记错的话，如果你有 N 个线性函数，你最多可以存储 N-1 个区间。而且，如果您确实有很多功能需要分析，那么您可以使用专门的数据结构来存储和搜索区间。

Answer 2

如果我理解正确，您的解决方案是对您的所有函数进行一些预处理，以便将域x拆分为范围，并且在每个这样的范围中，您都知道什么是最小函数。

实际上有两个阶段：“准备”和“查询”（给定特定x的结果）。

你的瓶颈是什么？

自然地，为了使“查询”阶段更快，您应该将您的范围组织成一种排序数组，以便您可以x在对数时间内通过中值搜索（或类似）找到包含给定值的范围。如果这是您所做的，但仍然不够快 - 请考虑代码级优化，因为从算法的角度来看，这似乎是最佳解决方案。

如果您的瓶颈是“准备”阶段 - 这里有优化的机会。据我了解，您会发现所有函数对的交集（在摆脱并行函数之后）。这并不是真正必要的。

考虑以下。首先，您按系数对所有函数进行排序（较高的系数位于开头）。摆脱并行功能。接下来构建范围数组，同时遍历您的函数。

由于当前函数的系数最低（在那些已经分析过的函数中） - 当前函数将是最小的一个，x直到无穷大。所以它的范围应该是从一些x0到无穷大。找到那个x0。从数组中取出最后一个范围（属于先前处理的函数），并找到x0- 该函数与当前函数的交集。前一个范围缩小到x0. 如果该范围变得无效（范围开始大于x0） - 意味着该功能完全被遮挡。在这种情况下 - 删除该范围，然后重复该过程。

为了让事情更清楚，我将编写一个伪代码：

rangeArr是对数组F,X，而F是函数描述，X是函数范围的开始。函数范围的结束被认为是下一个范围的开始，最后一个函数范围的结束是+infinity。

for each F sorted by coefficient
{
    double x0;

    while (true)
    {
        if (rangeArr is empty)
        {
            x0 = -inf;
            break;
        }

        FPrev = rangeArr.back().F;
        xPrev = rangeArr.back().X;

        x0 = IntersectionOf(F, FPrev);

        if (x0 > xPrev)
            break;

        rangeArr.DeleteLastRange();
    }

    rangeArr.InsertRange(F, x0);
}