Любая идея, какова временная сложность для этого рекурсивного алгоритма, пожалуйста?
/ * Функция f (x) является унимодальной в диапазоне [min, max] и может быть оценена в Θ (1) время * ε> 0 - точность алгоритма, обычно ε очень мало * max> min * n = (max - min) / ε, n> 0, где n - размер задачи * /
Algorithm(max, min){
if ((max - min) < ε){
return (max - min)/2 // return the answer
}
leftThird = (2 * min + max) / 3 // represents the point which is 1/3 of the way from min to max
rightThird = (min + 2 * max) / 3 // represents the point which is 2/3 of the way from min to max
if (f(leftThird) < f(rightThird))
{
return Algorithm(max,leftThird) // look for the answer in the interval between leftThird and max
}
else
{
return Algorithm(min, rightThird) // look for the answer in the interval between min and rightThird
}
}