math - 平面的交点

Question

我试图找出二次选择算法何时比线性选择算法更快。运行一些实验，我生成了两个 3D 图，显示了算法运行时间作为输入数组大小和所需顺序统计量的函数。使用 gnuplot 绘制绘图我确认存在二次算法更快的情况。然后，我使用 gnuplot 的拟合算法找到了两个模拟我观察到的运行时的函数（a、b、c、d、e、f 是我已经找到但省略的常量）：

lin_alg_runtime(x,y) = a x + b y +c

quad_alg_runtime(x,y) = (d*x * e*y) + f

其中 x 是输入数组的大小，y 是顺序统计量。

现在我有点迷失如何使用这些模型来计算何时在二次实现和线性实现之间切换。我怀疑我必须找到这两个函数相交的位置，但我不太确定该怎么做。如何找到这两个功能相交的地方？

Answer 1

基本上，您想使用运行时估计值最低的算法。

您可以只计算每个估计运行时间的值，并使用具有最低值的算法。您可以稍微简化一下。

您想在以下情况下使用四边形算法：

qual_alg_runtime(x,y) < lin_alg_runtime(x,y)
ax + by + c < dxey + f
ax + by -dexy + c-f < 0

因此，您可以计算ax + by -dexy + c-f，如果它小于零，请使用二次算法。