algorithm - 是否有可能在这种单调的非线性趋势上实现比 logn 搜索更好的性能？

Question

我的问题

(您可以跳过此部分并转到下一部分以了解实际问题。这只是为那些真正想知道“您到底为什么要问这个？”的人提供的背景信息)

想象一个物体从无摩擦的山坡上滑下。有加速度为 0 的平坦区域。其余路径的加速度大于 0，最高可达 9.81 m/s^2。如果你知道山的形状，你可以绘制最大加速度作为下山位置的函数。假设您将同一座山放在另一个星球或月球上以获得不同的加速度与位置曲线。为什么？目标是选择正确的加速度，以便您在 10 秒内到达山脚。你的位置变化是固定的。您的初始速度为 0，您的最终速度无关紧要，只要您在 10 秒内下山即可。假设您永远不会失去与山表面的联系。

这意味着您可以插入加速度值(改变行星)并在下坡行驶 10 秒后获取位置。当我绘制这种关系时，我得到一个单调递增的图(x 轴上更高的加速度导致 y 轴上更高的 10 秒位置变化值)。但是，我的山非常复杂。我不能假设这种关系是立方的或平方的。但它是单调递增的。

这是一些示例数据，其中包含我的算法绘制的图表:

acc = [
 1.5000    2.0000    2.5000    3.0000    3.5000    4.0000    4.5000
 5.0000    5.5000    6.0000    6.5000    7.0000    7.5000    8.0000
 8.5000    9.0000    9.5000   10.0000   10.5000   11.0000   11.5000
12.0000   12.5000   13.0000   13.5000   14.0000   14.5000   15.0000
15.5000   16.0000   16.5000   17.0000   17.5000   18.0000   18.5000
]

pos = [
 5.9176    6.5810    6.9784    7.2429    7.4314    7.5725    7.6818
 7.7691    7.8402    7.8992    7.9489    7.9913    8.0279    8.0597
 8.0877    8.1123    8.1342    8.1538    8.1714    8.1872    8.2016
 8.2146    8.2265    8.2374    8.2472    8.2550    8.2617    8.2676
 8.2676    8.2676    8.2676    8.2676    8.2676    8.2676    8.2676
]

显然我使用的是 Matlab，但这是独立于语言的。请注意，我的数据来 self 当前的算法，与我上面描述的问题略有不同。

一般化的问题

给定具有非线性和非线性化趋势的单调递增或递减函数，是否有类似于插值搜索 (loglogn) 的搜索算法，或者至少优于二进制/黄金截面搜索 (logn) 将找到正确的输入以实现所需的输出？

我的直觉是应该有比 logn 更好的东西可用，因为它是单调的和趋势的。我知道趋势不是一个很好用的词，但我认为它传达了我想表达的意思。

注意事项:

1. 了解从 x 计算 y 的计算成本非常高可能会有所帮助

更新

如果没有线性化，我无法在这个特定趋势上实现比 logn 更好的性能。虽然通过反转加速度值可以将数据线性化，但@Gassa 建议的 Newton-Raphson 类型方法并不成功，因为函数的导数计算成本高/不可能。

不幸的是，这并没有回答它是否不可能的问题。对于 f 和 f' 的计算时间昂贵的单调趋势，可能会找到一个 loglogn 搜索算法。这个问题需要数学证明。也许是时候把这个问题带到数学堆栈交换站点了。

虽然这里还有一个更深层次的问题需要回答，但我相信@Penguino 的回答的贡献使我找到了一种线性化数据的方法，以便我可以使用插值搜索。因此，他的答案已被标记为正确。

Answer 1

因此，如果我理解，您有一个函数 A(x)，它在两个限制 x0 和 x1 之间单调递增，并且对于这些限制之间的所有 x 也大于零。并且您的对象在 x0 和 x1 之间经历加速度 k.A(x)，其中 k 是与局部重力相关的比例因子。 And you want your object to start at velocity v0=0, at time t0=0, at position x0, and end up at position x1 at time t1 = 10 by appropriate choice of the scaling factor k.

如果是这种情况，那么我相信旅行时间与 1/sqrt(k) 成正比。因此，您需要做的就是针对某个任意 k 非常准确地一次准确计算旅行时间，然后适本地缩放。例如，如果k=1的行程时间为T1，那么k=(T1)^2/100的行程时间为10秒。

所以所需的时间是对旅行时间进行一次准确计算所需的 O(?)(大概一些分段数值积分可以做到这一点)。