algorithm - 应用于 double 时，三元搜索的时间复杂度是多少？

Question

我知道普通三元搜索的时间复杂度是 O(log3 n)，但是如果它与浮点数一起使用呢？
一个例子:这个代码块的这个块的时间复杂度是多少？

double s = -100, m1, m2, e = 100, EPS = 1e-6; 
while(abs(s-e) > EPS)
{     
    m1 = s + (e - s) / 3;
    m2 = e - (e - s) / 3;

    if(condition)
        e = m2;
    else
        s = m1;
}

所有这些都是在 -100 和 100 之间搜索一个实数，但是当 EPS 的精度改变时，时间复杂度会发生变化。变量变化。

Answer 1

复杂度是O(log 3(e-s)/EPS) .我们可以将问题简化为整数情况，其中 n=ceil((e-s)/ESP) . (这里 ceil(x) 是将 x 映射到下一个整数 j 使得 x <= j < x+1 的函数。)
让 delta = (e-s)/n <= EPS .很容易验证 delta <= EPS .在 i算法的第 th 步，或者 s[i]或 e[i]已从其前身( s[i-1] 或 e[i-1] )移动到不同的区间 I[i]由 I[i] = (s+(i-1)*delta, s+i*delta] (i <= n) 提供, 否则 s[i]和 e[i]都在 delta 以内彼此之间，在这种情况下，它们在 EPS 内彼此的。