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个(常数(，则该特定行上的工作量(单个比较(永远不会改变。因此其时间复杂度为CCD_ 3。
然而，可能会发生变化的是该行的执行次数！当n乘以O(1)运算时，总的时间复杂度仍然是O(n)。