前缀和算法时间复杂度分析：我的推导思路是否正确？

首先先把你提到的伪代码明确出来：

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

嘿，你的推导思路整体是正确的！咱们来把逻辑理得更清晰一点：

• 先算清楚实际的总计算量：第0次循环（i=0）只需要做1次加法操作，第1次循环要做2次加法……第n-1次循环要做n次加法。总加法次数是等差数列求和：$(n*(n+1))/2 = (1/2)n² + (1/2)n$。
• 你说「总计算量为n² + f(n)，其中f(n)是次数不超过n²的多项式」，这个表述虽然可以更精准（其实f(n)是低阶线性项加上调整系数的二次项），但核心逻辑没问题——大O复杂度只关注增长速度最快的主导项，这里主导项是n²，不管低阶项和系数是什么，我们都可以直接忽略它们，所以时间复杂度就是O(n²)。
• 你的最终结论完全正确：这个算法的时间复杂度确实是O(n²)。

内容的提问来源于stack exchange，提问作者bullbo