我编写了python代码以在列表中找到最大元素

问题描述 投票:1回答:2

您能告诉我代码的时间复杂度,我正在使用分治法吗?

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)
python algorithm recursion divide-and-conquer
2个回答
0
投票
由于这是递归算法,因此您需要使用主定理:

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的更多信息


0
投票
作为附带说明,您必须考虑到此算法的代码复杂性仅对大量元素有用。如果您的元素数量很少,则线性算法会更有效,因为它省去了过程中的递归。
© www.soinside.com 2019 - 2024. All rights reserved.