对数组进行两次二分查找的时间复杂度是多少？

Question

我有一个对有序时间列表进行操作的函数。该函数将某个时间作为参数传递，并返回该特定时间在数组中出现的次数。

我的函数对列表执行两次二分搜索，一次查找特定时间的上限，另一次查找下限。

这个函数的时间复杂度是多少？我知道二分搜索的时间复杂度为 log2(n) 但我不确定执行两次会如何影响时间复杂度。只是 log2(2n) 吗？

    def count_time(time):

        return self.upper_bound(time) - self.lower_bound(time)

Answer 1

执行两次二分搜索而不是一次不会影响渐近复杂度；它只是因子 2，您可以忽略它：

O(2log₂𝑛) = O(log₂𝑛) = O(log𝑛)

此外，对数的底数与 Big O 表示法无关，因此您可以将其省略。