前缀总和时间复杂度

Question

我在阅读this，在最后一部分练习。

我对时间复杂性很陌生。

首先溶液说，机器人将在一个方向上在另一方向上从0移动p次，然后m - p，对于p到m，对我来说这是：

sums = [] 
for left in 0..m 
    sums[left] = 0 
    for right in 0..(m-left) 
    sums[left] += A[k - left + right] || 0 
    A[k - left + right] = 0 

A是输入阵列，k是一个初始位置，即一个给定的常数。

从我了解的复杂性将是：

O(m + m+(m-1)+(m-2)+...+3+2+1) 
    | ----------------------- 
    |    | 
    because  because the inner loop 
    first loop 

O(m + (m*(m+1))/2) 
O(m + (m*(m+1))/2) 
O(m^2) ? 

什么这里是我的错误？

此问题的解决方案指出复杂度为O(n*m)，您能解释我为什么吗？

Answer 1

the goal is to calculate the maximum sum that the robot can collect in m moves. 

就这样，我明白该算法将是这样的：

max=0; 
for i in 1..n 
    for j in 1..m 
     sum+=A[i] 
    end loop; 
    if sum>max then 
     max=sum; 
    end if; 
    sum=0; 
end loop; 

，它是一个O（N * M）的问题（如果我理解正确的问题）