二分查找的时间复杂度是多少？

Question

def binsearch(a):
    if len(a) == 1:
        return a[0]
    else:
        mid = len(a)//2
        min1 = binsearch(a[0:mid])
        min2 = binsearch(a[mid:len(a)])
        if min1 < min2:
            return min1
        else:
            return min2

我试图提出 min1 < min2 的时间复杂度，我觉得它是 O(n) 但我不太确定它是否正确。有人可以尝试向我解释如何计算此类代码的时间复杂度吗？

Answer 1

如果min1和min2是数字，并且总是有 2 个（常量），则该特定行（单个比较）上的工作量永远不会改变。因此它的时间复杂度为O(1)。

然而，可能会改变的是该行的执行次数！当您有n时间进行O(1)操作时，总体时间复杂度仍然是O(n)。