二分查找的时间复杂度是多少？
What is the time-complexity in a binary search?
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)，但我不太确定它是否正确。有人可以尝试向我解释如何计算此类代码的时间复杂度吗？
如果 min1 和 min2 是数字，并且总是有 2 个（常数），则该特定行（单次比较）的工作量永远不会改变。因此其时间复杂度为O(1).
然而，可能改变的是该行被执行的次数！当你有 n 次 O(1) 操作时，整体时间复杂度仍然是 O(n).
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)，但我不太确定它是否正确。有人可以尝试向我解释如何计算此类代码的时间复杂度吗？
如果 min1 和 min2 是数字，并且总是有 2 个（常数），则该特定行（单次比较）的工作量永远不会改变。因此其时间复杂度为O(1).
然而，可能改变的是该行被执行的次数！当你有 n 次 O(1) 操作时，整体时间复杂度仍然是 O(n).