如何以O(log n)时间复杂度求解严格增减函数和的最小值

存在时间复杂度为O(log n)的求解方法，可通过二分查找实现。 #

令目标函数为 h(x) = f(x) + g(x)，我们可以通过相邻点的h值比较，不断收缩最小值所在的区间：

• f是严格递增函数，x增长时f的增量恒为正
• g是严格递减函数，x增长时g的减量恒为正
• 如果 h(mid) < h(mid + 1)：说明x从mid增长到mid+1时，f的增量已经超过了g的减量，最小值必然落在左半区间（包含mid），因此将右边界收缩到mid
• 如果 h(mid) > h(mid + 1)：说明x从mid增长到mid+1时，g的减量仍大于f的增量，最小值必然落在右半区间（包含mid+1），因此将左边界收缩到mid+1

每次操作都会将区间长度缩短至少一半，整体仅需要O(log n)次迭代，每次迭代仅调用2次黑盒函数（单次调用时间复杂度O(1)），整体时间复杂度符合要求。 #

def find_optimal_x(n: int, f, g) -> int:
    left, right = 0, n
    while left < right:
        mid = (left + right) // 2
        h_mid = f(mid) + g(mid)
        h_mid_next = f(mid + 1) + g(mid + 1)
        if h_mid < h_mid_next:
            right = mid
        else:
            left = mid + 1
    return left

• 当n=0时，算法直接返回0，符合预期
• 当h(x)全程递减时，算法会逐步收缩左边界直到返回n
• 当h(x)全程递增时，算法会逐步收缩右边界直到返回0

内容的提问来源于stack exchange，提问作者user16830227