Является ли троичный поиск менее эффективным, чем этот связанный алгоритм?

Алгоритм троичного поиска - это быстрый алгоритм для поиска минимума или максимума унимодальной функции , функции, которая либо увеличивается, а затем уменьшается, либо уменьшается, а затем увеличивается. Предположим, что мы имеем дело с функцией, которая уменьшается, а затем увеличивается, и что мы хотим найти минимум значения. Тернарный поиск работает с использованием следующей рекурсии:

• Если размер окна «достаточно мал», просто верните его среднюю точку.
• В противном случае:
  • Оцените функцию на левой и правой границах; назовем значения l и r.
  • Оцените функцию в точках 1/3 и 2/3; назовите значения m ₁ и m ₂
  • Если m ₁ 2 , то мы находимся в области возрастания функции и минимум не может быть между m ₂ и r.
  • Если m ₁ > m ₂ , то мы находимся в области убывания функции. Может ли минимум быть между l и m ₁
  • Рекурсивно ищите 2/3, которые не были отброшены.

Этот алгоритм работает быстро, потому что он может отбрасывать 1/3 значений на каждой итерации.

Однако мне кажется, что я чего-то упускаю, потому что считаю, что мы можем заставить этот алгоритм работать намного быстрее. В частности, обратите внимание, что мы всегда отбрасываем одну из третей диапазона между границей и одной из точек измерения. Это означает, что мы сохраняем область между точкой зондирования и другой границей. Поскольку троичный поиск выбирает пробные точки в 1/3 точек, это означает, что мы сохраняем 2/3 значений в каждой точке. Что, если вместо того, чтобы исследовать точки 1/3 и 2/3, мы будем исследовать точки 1/2 - ε и 1/2 + ε на предмет чрезвычайно малого ε? Это будет означать, что мы будем отбрасывать 1/2 - ε диапазона на каждом шаге, а это означает, что размер диапазона будет уменьшаться намного быстрее, чем если бы мы просто каждый раз отбрасывали 1/3 элементов.

В качестве примера, если я выберу ε = 1/1000, мы выберем 999/2000 из диапазона для поиска на каждой итерации.Здесь показана доля, оставшаяся после некоторого количества итераций (троичный поиск находится слева, мой алгоритм - справа :)

 1 :                1.0  >=                1.0
 2 :     0.666666666667  >=             0.5005
 3 :     0.444444444444  >=         0.25050025
 4 :     0.296296296296  >=     0.125375375125
 5 :     0.197530864198  >=    0.0627503752501
 6 :     0.131687242798  >=    0.0314065628127
 7 :    0.0877914951989  >=    0.0157189846877
 8 :    0.0585276634659  >=   0.00786735183621
 9 :    0.0390184423106  >=   0.00393760959402
10 :    0.0260122948737  >=   0.00197077360181
11 :    0.0173415299158  >=  0.000986372187705
12 :    0.0115610199439  >=  0.000493679279947
13 :   0.00770734662926  >=  0.000247086479613
14 :   0.00513823108617  >=  0.000123666783046
15 :   0.00342548739078  >=  6.18952249147e-05
16 :   0.00228365826052  >=  3.09785600698e-05
17 :   0.00152243884035  >=  1.55047693149e-05
18 :   0.00101495922690  >=  7.76013704213e-06
19 :  0.000676639484599  >=  3.88394858959e-06

Эта модифицированная версия алгоритма просто «лучше», чем исходная версия? Или мне здесь не хватает чего-то, что означало бы, что мне не следует использовать модифицированную стратегию для выбора точек исследования?