二分次数 $\times$ 单次 check 复杂度
二分次数一般都是 $\log n$ 的，和 eps 没有太大关系。
by SlaineTroyard @ 2023-10-30 11:27:47
和 eps 有关系，时间复杂度计算公式为
$$O(n\log\dfrac{w}{\varepsilon})$$
其中 $w$ 是枚举的区间长度，$\varepsilon$ 是区间终止长度。
by Terrible @ 2023-10-30 11:48:59
@[SlaineTroyard](/user/450246) 哦忘了写上check复杂度了/kk
谢谢两位大佬/bx
by Kniqht @ 2023-10-30 11:51:43
由于不需要实现高精度浮点类型，因而 $\varepsilon$ 总是不能够足够小的，它不能小于浮点数的最小精度，因而取一个可行的下界值并可视为常数。
进一步地可以说，和数据类型（例如 `int32`、`int64`）绑定的时间复杂度都可以视为 $\Theta(1)$ 的，原因则是这个算法一定有一个上界，有上界就是 $\Theta(1)$ 的。（即便可能得运行时间是几个世纪）
将“估计运行时间大小的时间复杂度理解”和“算法本身的严格的时间复杂度”混为一谈是不正确的。
by Terrible @ 2023-10-30 11:57:40
哦是这样的，一般 eps 取得越精确二分次数就越多。不过可以限定二分次数。（）
by SlaineTroyard @ 2023-10-30 12:00:10