2

问题：给定一个n次多项式（系数从 a 0到a n-1），保证从x = 0 增加到x max，找到前m个等距y点的最有效算法是什么值（即y i - y i-1 == c，对于所有i）？

示例：如果我希望间距为c = 1，并且我的多项式为f(x) = x^2，那么前三个点将位于y =1 ( x =1)、y =2 ( x ~=1.4142) 和y =3 ( x ~=1.7321)。

我不确定它是否重要，但我的具体问题涉及具有给定系数的多项式的立方。我的直觉告诉我，最有效的解决方案应该是一样的，但我不确定。

我正在解决 ACM为 2012 年世界总决赛设置的问题（问题 B）中的问题，所以这主要是因为我很好奇。

编辑：我不确定这是否应该出现在Math SE上？

4

1 回答 1

3

您可以使用二进制搜索找到给定 Y 的 X。它是对数时间复杂度，与 x 值范围的大小成正比，除以您的误差容限。

def solveForX(polyFunc, minX, maxX, y, epsilon):
    midX = (minX + maxX) / 2.0
    if abs(polyFunc(midX) - y) < epsilon:
        return midX
    if polyFunc(midX) > y:
        return solveForX(polyFunc, minX, midX, y, epsilon)
    else:
        return solveForX(polyFunc, midX, maxX, y, epsilon)

print solveForX(lambda x: x*x, 0, 100, 2, 0.01)

输出：

1.416015625

编辑：在评论中扩展一个想法，如果你知道你将搜索多个 X 值，可以缩小 [minX, maxX] 搜索范围。

def solveForManyXs(polyFunc, minX, maxX, ys, epsilon):
    if len(ys) == 0:
        return []
    midIdx = len(ys) / 2
    midY = ys[midIdx]
    midX = solveForX(polyFunc, minX, maxX, midY, epsilon)
    lowYs = ys[:midIdx]
    highYs = ys[midIdx+1:]
    return solveForManyXs(polyFunc, minX, midX, lowYs, epsilon) + \
    [midX] + \
    solveForManyXs(polyFunc, midX, maxX, highYs, epsilon)

ys = [1, 2, 3]
print solveForManyXs(lambda x: x*x, 0, 100, ys, 0.01)

输出：

[1.0000884532928467, 1.41448974609375, 1.7318960977718234]
于 2012-08-08T15:56:08.493 回答