1

想象一下有一个在 [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;
}
4

2 回答 2

5

Suppose there was such an algorithm, that is, an algorithm that can find the maximum of an approximation of a continuous function without looking at every point of the approximation.

Now choose a positive integer n and choose any finite sequence of n doubles you care to name. There are infinitely many continuous functions such that f(n) is equal to the nth double in the sequence, and smaller than or equal to the largest of them everywhere. Choose one of them.

Now use your algorithm to find the largest double of the n doubles. By assumption, it examines fewer than n of the doubles. Let's suppose it examines all of them except the kth double.

Now suppose we create a new sequence identical to the first one except that the kth double is the maximum. Is the algorithm magical, that when given an input that it does not read, it changes its output?

Now is it clear why there is no such algorithm? If you want to find the longest piece of string in the drawer, you're going to have to look at all of them.

The continuity of the function doesn't help you at all. All continuity gives you is a guarantee that given a point on the function, you can find another point on the function that is as close to the first point as you like. That tells you nothing about the maximum value taken on by the function. (Well, OK, it tells you something. On a closed bounded interval it implies that a maximum exists, which is something. But it doesn't help you find it.)

于 2013-10-03T06:28:33.990 回答
2

鉴于您正在谈论的函数是代码，那么不，该函数可以在任何时候返回任意最大值。

如果您可以对函数做出假设（例如最大变化率），那么您可以优化。

于 2013-10-03T03:03:40.433 回答