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)

score 3 · Accepted Answer

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

score 0 · Accepted Answer

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

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

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

为简单起见，假设所有 a[i] 元素都等于 1，所以如果我们在 i 为 0 到 n -1 时找到 b[i] 的总和，那么我们会找到第三行运行的次数。

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

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

2 回答 2