我的算法是线性时间吗？

Question

# given an array, it solves sum of elements in it, 
# args: array, initial and final indices
# Returns: sum of elements
def ArrayTot (arr, low, high):
    return sum( arr[low : high+1] )

# Is this linear time?
# args: array, initial and final indices
# returns: Max possible value in sub-array.
def MaxSubArray (arr, low, high):
    # max value of sub-array
    TotalArray = 0
    # starts iterating arr from left - right i.e., arr[low, j]
    for j in xrange(low, high+1):
        # finds sum of sub array arr[low,j]
        tot = ArrayTot (arr, low, j)
        # Iterates the sub-array arr[low,j] so as to find any other possible arr[i,j] which results max value
        for i in xrange(low, j+1):
            SubArrTot = ArrayTot(arr, i, j)
            if SubArrTot >= tot:
                tot = SubArrTot
        if tot >= TotalArray:
            TotalArray = tot
    return TotalArray

arr = [13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]
low = 0
high = 15

print MaxSubArray(arr, low, high)

我正在学习算法(书:算法导论)..所以,我应该在给定的数组中找到一个构成最大和的子数组.是的,非递归的线性时间算法.

这就是我所做的(如上所示)..但在我的解决方案中,for循环内部有一个for循环,并且两个迭代'n'项.

如果我没有错,那应该O(n^2)是不是线性的!在那种情况下,我该如何解决呢？

Answer 1

这当然不是线性解决方案.解决这个问题的线性时间算法之一被称为Kadane算法.

即使只是这一点代码

for j in xrange(low, high+1):
    tot = ArrayTot (arr, low, j)

已经有Theta(n^2)时间复杂性了.