c++ - 超出三次函数根二等分搜索时间限制
问题描述
我已经实现了这个解决方案来查找三次函数的根
f(x) = ax3 + bx2 + cx + d
给定a
, b
, c
, and 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;
}
解决方案
无需确定初始间隔,只需[-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
。这种情况不需要特殊处理。
推荐阅读
- linux - 如何将 wget 输出重定向到新创建的目录
- r - 如何在 R 中使用 ggplot2 创建散点图?
- java - 为什么if else语句在这个程序中不起作用。请需要一些解释,虽然我无法继续学习
- r - 如何保存 ShinyFiles 目录输入的基本名称以传递给函数
- amdp - AMDP 选择查询正在获取错误的记录
- c# - 计算 CRC64 以匹配报告中给出的 Azure 值
- python - Python 魔术函数 vs %%writefile
- node.js - 未捕获的错误:连接失败。rtcpeerconnection.t._pc.onconnectionstatechange
- python - 如何确定使用 python 和 jinja 运行的 logstash 实例
- node.js - 在 mongoose 上使用 MongoDB Node.js 驱动程序的优缺点,反之亦然