前綴總和時間複雜度

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）的問題（如果我理解正確的問題）