三次函数根二分搜索超出时间限制

Question

我已经实现了这个解决方案来查找三次函数的根

f(x) = ax3 + bx2 + cx + d

给定a、b、c和d，确保它是单调的。

在将解决方案提交给在线法官而没有显示测试用例后，我遇到了时间限制错误。a、b、c、 并d保证该函数是单调的并且我们知道它是连续的。该代码首先找到区间[A, B]使得f(A) * f(B) < 0；然后代码开始实现二分搜索。

我想知道是否有可能最小化我的代码的时间复杂度，以便它通过在线判断。输入是a, b, c, d，输出应该是有错误的根0.000001。

代码：

#include <iostream>
#include <algorithm>
//#include <cmath>
//#include <string>

using namespace std;

int f(double a, double b, double c, double d, double x) {
    return x*(x*(a*x + b) + c) + d;
}

int main() {

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    double a, b, c, d, A, B, x = 1, res;
    cin >> a >> b >> c >> d; 

    //determinning the interval
    double f_x = f(a, b, c, d, x);
    if (a > 0) { // strictly increasing
        if (f_x > 0) { B = 0;
            while (f(a, b, c, d, x) >= 0) { x -= x; }
            A = x; }
        else { A = 0;
            while (f(a, b, c, d, x) <= 0) { x += x; }
            B = x; }
    }

    else { //strictly decreasing
        if (f_x > 0) { A = 0;
            while (f(a, b, c, d, x) >= 0) { x += x; }
            B = x; }
        else { B = 0;
            while (f(a, b, c, d, x) <= 0) { x -= x; }
            A = x; }    
    }
    // Bisection Search
    double l = A;
    while ((B - A) >= 0.000001)
    {
        // Find middle point 
        l = (A + B) / 2;

        // Check if middle point is root 
        if (f(a, b, c, d, l) == 0.0)
            break;

        // Decide the side to repeat the steps 
        else if (f(a, b, c, d, l)*f(a, b, c, d, A) < 0)
            B = l;
        else
            A = l;
    }
    res = l;
    cout.precision(6);
    cout << fixed << " " << res;

    return 0;
}

Answer 1

不需要确定初始区间，取 即可[-DBL_MAX, +DBL_MAX]。容差可以选择为 1 ULP。

下面的代码实现了这些想法：

// This function will be available in C++20 as std::midpoint
double midpoint(double x, double y) {
    if (std::isnormal(x) && std::isnormal(y))
        return x / 2 + y / 2;
    else
        return (x + y) / 2;
}

int main() {
    ...
    const auto fn = [=](double x) { return x * (x * (x * a + b) + c) + d; };

    auto left  = -std::numeric_limits<double>::max();
    auto right =  std::numeric_limits<double>::max();

    while (true) {
        const auto mid = midpoint(left, right);
        if (mid <= left || mid >= right)
            break;

        if (std::signbit(fn(left)) == std::signbit(fn(mid)))
            left = mid;
        else
            right = mid;
    }

    const double answer = left;
    ...
}

最初，fn(x)可以溢出并返回inf。这种情况不需要特殊处理。