二维数组的线性算法

Question

我有一个用整数（A至A[0]）填充的一维数组A[n]。我被问到设计一个线性算法，该算法可以生成2D数组B，其中B[i][j] = A[i] + ... + A[j]为0 <= i < j <= n。因此，这意味着我需要遍历对角线上方的所有元素，因此(n-1) x n x (1/2)元素也应为O(n^2)。我通过以下方法启动了算法（伪代码）：

for i=0 to n-1:
    for j=i+1 to n:
        // do calc

但是这已经是O(n^2)，甚至可以线性时间吗？

Answer 1

由于要以n^2的大小填充2D数组，因此算法的时间复杂度为Omega(n^2)。因此，在当前规范下不可能在线性时间内运行此算法。