Временная сложность для анализа рекурсивного алгоритма - PullRequest
0 голосов
/ 01 мая 2020

Любая идея, какова временная сложность для этого рекурсивного алгоритма, пожалуйста?

/ * Функция 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
 }

}

...