algorithm - 如何最小化已知为 U 形的整数函数？

Question

设 f 是定义在非负整数 n ≥ 0 上的函数。假设已知 f 是 U 形的(凸的并最终增加)。如何找到它的最小值？也就是说，对于所有 n，m 使得 f(m) ≤ f(n)。

U 型函数的例子:

• n**2 - 1000*n + 100
• (1 + 1/2 + ... + 1/n) + 1000/sqrt(1+n)

当然，人类数学家可以尝试使用微积分来最小化这些特定函数。不过，对于我的计算机，我想要一个可以最小化任何 U 形函数的通用搜索算法。

---

这些函数在 Python 中再次出现，以帮助任何想要测试算法的人。

f = lambda n: n**2 - 1000*n + 100
g = lambda n: sum(1/i for i in range(1,n+1)) + 1000/sqrt(1+n)

不一定需要答案中的代码(任何语言)，只需对算法进行描述即可。我会对这些特定功能的答案感兴趣。

Answer 1

您可能正在寻找 ternary search .
三元搜索将有助于在 O(logN) 时间内根据您的要求找到 f(m)，其中 N 是曲线上的点数.

它基本上取 (l,r) 范围内的两个点 m1 和 m2，然后在 1/3 rd 部分递归搜索。

python 代码(来自维基百科):

def ternarySearch(f, left, right, absolutePrecision):
    while True:
        #left and right are the current bounds; the maximum is between them
        if abs(right - left) < absolutePrecision:
            return (left + right)/2

        leftThird = (2*left + right)/3
        rightThird = (left + 2*right)/3

        if f(leftThird) < f(rightThird):
            right = rightThird
        else:
            left = leftThird