找到最小的功能

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

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

\n\n

编辑-\n详细说明，如果您要求解 x 的任意一对函数，则 x 表示这两个函数中的一个大于另一个的值。将存在可定义的区间，其中区间内所有值的最小函数都相同。

\n\n

这是 3 个示例函数的图。\n

\n\n

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

\n\n

(-\xe2\x88\x9e, 7/3]     => 5x - 6\n(7/3, \xe2\x88\x9e]      => 2x + 1\n

\n\n

现在，在运行时，您只需执行“q 属于什么区间” ，而不是“ x = q 处的最小函数是什么”。

\n\n

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

\n