Квадрарный поиск

[dimag0g]

Оптимальный вариант решения задачи поиска минимума — деление отрезка золотым сечением. Ваш вариант сокращает отрезок вдвое за три вычисления функции, а метод золотого сечения — более чем вчетверо. en.wikipedia.org/wiki/Golden_section_search

[dimag0g]

Поправлюсь: Ваш вариант сокращает отрезок вдвое за два вычисления функции, а метод золотого сечения — в 2.62 раза.

[Sammarize]

о да, Вы правы. Спасибо за замечание.
Правда, мой метод использует для этого не 2 вызова функции, а, в среднем, несколько меньше. Но, вероятно, метод золотого сечения действительно быстрее — там та же идея, которая является ключевой в моём методе, использована ещё лучше.

[mt_]

Оптимизация имеет право на существование в определённом классе задач.
Хочу также отметить, что уменьшение количества расчётов значения функции идёт за счёт использования дополнительной памяти: на «глубоких» шагах рекурсии количество хранимых значений может в общем случае быть довольно большим. Поэтому ваша оптимизация (уменьшение числа расчётных точек) будет работать только в том случае, если число шагов рекурсии будет гарантированно меньше соответствующего ему объёма памяти.

[mt_]

… объёма памяти, который мы можем выделить для расчёта.

[Sammarize]

Вы правы. Однако, надо заметить, что тот же недостаток имеется и у тернарного поиска (правда, в меньшей степени), и у метода золотого сечения. Кроме того надо заметить, что этот метод допускает и нерекурсивную реализацию (что, опять же, в равной степени касается и тернарного поиска и поиска золотого сечения):

double quadSearch(double L, double R) {
	double midValue = f((L + R)/2);
	double leftValue;
	double rightValue;
	while (R - L > eps) {
		leftValue = f((3*L + R)/4);
		if (leftValue < midValue) {
			midValue = leftValue;
			R = (L + R)/2;
		} else {
			rightValue = f((L + 3*R)/2);
			if (rightValue > midValue) {
				midValue = rightValue;
				L = (R + L)/2;
			} else {
				L = (3*L + R)/4;
				R = (L + 3*R)/4;
			}
		}
	}
	return (R + L) / 2;
}