algorithm - 前缀和算法的时间复杂度

Question

鉴于以下伪代码，我想知道在尝试确定时间复杂度时我的思维过程是否正确。

for i = 0 to n-1
   Add the numbers A[0] thru A[i].
   Store the result in B[i].

该算法将循环 n 次，并且由于最后一次迭代将需要最多的计算(n 次计算)，该算法将总共进行 n^2 + f(n) 次计算。其中 f(n) 是 n^2 或更小的多项式。 因此该算法是二次的 O(n^2)。

Answer 1

由于 Add the numbers A[0] thru A[i]. 的时间复杂度为 \Theta(i)，因此您的代码的时间复杂度为\Theta(1 + 2 + 3 + ... +\Theta(n)) =\Theta(n^2)。因此，您对代码的分析是正确的。