对有序时间列表执行两次二分查找的时间复杂度是多少？

问题背景 #

你实现了一个操作有序时间列表的函数count_time，它接收一个时间参数，返回该时间在数组中的出现次数。函数内部通过两次二分查找（分别调用upper_bound和lower_bound）确定目标时间的上下界，再通过差值得到次数。已知单次二分查找的时间复杂度是O(log₂n)，你想知道执行两次后的时间复杂度是不是O(log₂(2n))。

核心结论 #

两次二分查找后的时间复杂度不是O(log₂(2n))，而是O(log₂n)

具体解释 #

1. 大O时间复杂度关注的是输入规模n趋近于无穷大时的渐近增长趋势，会直接忽略常数系数和固定的常数项。
2. 单次二分查找是O(log₂n)，两次执行的总复杂度就是O(2×log₂n)，这里的常数系数2会被大O表示法忽略，所以最终还是O(log₂n)。
3. 至于log₂(2n)，展开后是log₂2 + log₂n = 1 + log₂n，其中的常数项1同样会被大O规则忽略，所以O(log₂(2n))其实和O(log₂n)是等价的，但这不是两次二分查找复杂度的正确推导逻辑——两次查找的复杂度是O(log₂n)，是因为常数系数被忽略，而非等于log₂(2n)。

你的函数代码 #

def count_time(time):
    return self.upper_bound(time) - self.lower_bound(time)

内容的提问来源于stack exchange，提问作者beugo