时间戳

首页 > 解决方案 > 函数 maxsubarray 的时间复杂度

python - 函数 maxsubarray 的时间复杂度

问题描述

自从我第一次使用 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)

标签： pythonalgorithmtime-complexity

解决方案

让我们逐步检查您的代码以找出时间复杂度。

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)时间复杂度，因为您必须再次遍历列表。

总体而言，您的代码O(n)在 for 循环中执行需要时间复杂度的操作，这也需要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]

推荐阅读