想象一下有一个在 [0.0,n] 范围内连续的函数。s
是否有任何算法可以比简单迭代更快地找到给定最小步长的函数的最大值?简单的迭代很容易编程,但是时间复杂度n / s
很大时会增加。
double maxValue = 0;
double maxValueX = 0;
double s = 0.1 * n;
for (double x = 0.0; x <= n; x += s)
{
double value = someFunction(x);
if(value > maxValue) {
maxValue = value;
maxValueX = x;
}
}
我已经尝试过这种更快的方法,但不知道它是否会卡在局部最大值上。
double min = 0;
double max = n;
int steps = 10;
increment = (max - min) / steps;
while (increment > s)
{
double maxValue = 0;
double maxValueX = X;
for (double x= min; x <= max; x+= increment)
{
double value = someFunction(x);
if(value > maxValue) {
maxValue = value;
maxValueX = x;
}
}
min = Math.Max(maxValueX - increment, 0.0);
max = Math.Min(maxValueX + increment, n);
increment = (max - min) / steps;
}