maxsubarray函数的时间复杂度

Question

我很难计算这个函数的时间复杂度，因为我第一次使用sum()，所以sum接受一个列表sum(list[])并返回该列表的总和，并且具有O(n)的时间复杂度。如果它大于n^2有没有办法让它小于或等于n^2

def maxsubarray (inputlst):
size = len(inputlst)
minlist = [inputlst[0]]
globallist = [inputlst[0]]

for i in range(1,size):
minlist.insert(i,inputlst[i])
if (sum(minlist) > inputlst[i]):
if sum(minlist) > sum(globallist):
globallist = list(minlist)
if (sum(minlist) < inputlst[i]):
minlist = [inputlst[i]]
if sum(minlist) > sum(globallist):
globallist = list(minlist)

Answer 1

让我们一步一步地检查代码，找出时间复杂度。

class Solution(object):
def maxSubArray(self, inputlst):
size = len(inputlst)        # O(1)
minlist = [inputlst[0]]     # O(1)
globallist = [inputlst[0]]  # O(1)

for i in range(1,size):     # O(len(inputlst)) = O(n)
minlist.insert(i,inputlst[i])  # O(n) --> insert time complexity
if (sum(minlist) > inputlst[i]): # O(n) --> sum
if sum(minlist) > sum(globallist):  # O(n) --> sum
globallist = list(minlist)      # O(n)
if (sum(minlist) < inputlst[i]):  # O(n)
minlist = [inputlst[i]]
if sum(minlist) > sum(globallist):  # O(n)
globallist = list(minlist)      # O(n)
return sum(globallist)

平均而言，sum()函数的时间复杂度为O(n)，因为它遍历整个列表。insert(index, element)也需要O(n)的时间复杂度，因为插入到一个特定的索引可能需要将剩余的元素向右移动。使用list()创建列表需要O(n)的时间复杂度，因为您必须再次遍历列表。

总的来说，你的代码在for循环中执行的操作需要O(n)的时间复杂度，这也需要O(n)的时间复杂度。因此，您的解决方案的时间复杂度将是O(n^2)。对于最大子数组问题，这似乎是一个低效的解决方案。查看下面更简单、简短的解决方案:

class Solution:
def maxSubArray(self, nums):           
prev = nums[0]
max_ = prev
for i in range(1, len(nums)):
prev = max(prev + nums[i], nums[i])
if(max_ < prev): max_ = prev
return max_

逻辑很简单:为了找到最大的子数组，要么将当前项添加到子数组中，要么不添加。它被称为Kadane的算法。
由于您只遍历列表一次，时间复杂度为O(n)。此外，您不需要创建不必要的列表，两个变量(一个用于前一个数字，另一个用于最大总和)就足够了。
除了求和，如果你想返回最大的子数组，你可以保存两个对应于起始点和结束点的下标。

class Solution:
def maxSubArray(self, nums):           
prev = nums[0]
max_ = prev
start = 0
end = 0
start_max = 0
end_max = 0
for i in range(1, len(nums)):
if(prev + nums[i] >= nums[i]):
prev += nums[i]
end = i
else:
prev = nums[i]
start = i
end = i
if(max_ < prev):
max_ = prev
start_max = start
end_max = end
print(nums[start_max:end_max+1])
return max_

nums = [-2,1,-3,4,-1,2,1,-5,4]的输出:

[4,-1,2,1]