您能告诉我代码的时间复杂度,我正在使用分治法吗?
def max_of_list(l):
if(len(l)==1):
return l[0]
else:
left_max=max_of_list(l[:len(l)//2])
righ_max=max_of_list(l[len(l)//2:])
return max(left_max,righ_max)
T(n)= a T(n / b)+ f(n)
a:子问题的数量b:减少子问题的大小
此算法是递归的,因为f(n)的拆分/合并过程的复杂度为O(1)。因此,算法的复杂度为O(n ^ c),其中c是关键指数,由下式给出:
c =日志(a)/日志(b)
在这种情况下:
c = log(2)/ log(2)= 1
算法的复杂度是线性的:例如O(n)
您可以阅读有关Master theorem的更多信息