前缀和算法的时间复杂度

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)。因此，您对代码的分析是正确的。

Answer 2

我们可以用以下代码替换您的代码

    for i 0 to n - 1
        for j 0 to i
            b[i] += a[j]   <---

为了找到这个算法的大O我们需要计算多少执行第 3 行的次数。

为了简单起见，假设所有 a[i] 元素都等于 1 所以如果我们在 i 为 0 到 n -1 时找到 b[i] 的总和然后我们找到第 3 行运行.

的次数

i: b[i]
0: 1
1: 2
2: 3
..
n - 1: n

因此所有B[i]的总和为n * (n + 1) / 2 这是 O(n^2)

Time complexity of a prefix sum algorithm