函数 maxsubarray 的时间复杂度

Question

我很难计算这个函数的时间复杂度，因为我是第一次使用 sum()，所以 sum 需要一个列表 sum(list[]) 和 returns 该列表的总和时间复杂度为 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's Algorithm。
由于您只遍历列表一次，时间复杂度为 O(n)。此外，您不会创建不必要的列表，两个变量（一个用于前一个数字，另一个用于最大总和）就足够了。
除了求和，如果要return最大子数组，可以持有两个索引对应的起点和终点。

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]

函数 maxsubarray 的时间复杂度

Time complexity for the function maxsubarray

python

algorithm

time-complexity