前缀平均值从O(n^2)到O(n)：前缀和优化、递推平均与调试技巧

刷题刷到“10345 前缀平均值”这题的时候我第一反应是这不就是 LeetCode 上一维数组的动态和换了个马甲吗但真正动手写了几版实现、又跑到不同 OJ 上反复提交之后才发现这道题其实藏着不少值得掰开揉碎的东西。前缀平均值Prefix Average在算法教材里常被当作分析复杂度的入门案例很多人在初学阶段都写过“双层循环”的版本然后被 n10^5 的评测数据教做人。这篇文章我就从题目拆解讲起把暴力解法、前缀和优化、流式递推平均、多语言实现、边界条件和调试技巧一次性说清楚。1. 拆题前缀平均值到底在求什么1.1 从数组和前缀说起先说最基础的概念。我们拿到一个长度为 n 的数组 a前缀平均值就是对于每个下标 i计算从第一个元素到第 i 个元素的平均值然后把这个平均值放到答案数组的第 i 个位置。举个例子如果 a [10, 20, 30, 40, 50]那么前缀平均值数组是 [10, 15, 20, 25, 30]。为什么要叫“前缀”而不是“全部”因为每个位置只关心自己以及之前的那一段像往前看而不往后看。这个概念和“前缀和”是一对孪生兄弟前缀和求的是累计相加的结果前缀平均值求的是累计结果除以元素个数。从数据结构的角度看这题考察的是两个点第一能不能快速维护一个动态增长的“累计总和”第二能不能正确处理除法中的类型和精度问题。对于刚学编程的人来说最直观的写法是两层循环外层固定当前终点内层从起点累加最后除一下。这个写法没有错但它暴露了一个问题——一旦数组规模变大内层循环反复扫描已经算过的区域造成大量重复计算。1.2 10345 这个题号背后的考点“10345 前缀平均值”这个题号我在好几个 OJ 上都见过不同平台的编号不一样但题面几乎都是同一个套路输入一个整数数组输出它的前缀平均值。有些版本为了让题目看起来更“算法”会把长度限制在 10^5 甚至 10^6逼着你不去写那个 O(n^2) 的版本。这道题真正想考的并不是你会不会求平均值而是你有没有意识到“重复计算”是性能杀手。初学者最容易犯的错就是在内层循环里反复重新计算总和。假设 n 100000两层循环总共要执行大约 5×10^9 次加法这个量级在 C 里勉强能撑几秒在 Python 里基本就是超时警告。而如果你用前缀和一趟遍历就能把所有累计值记下来时间复杂度直接降到 O(n)。从 O(n^2) 到 O(n)这不是简单的常数级别优化而是量级的跨越数据规模一旦放大差别就是“能跑”和“不能跑”的分水岭。1.3 这题和前缀和的紧密关系前缀平均值本质上就是“前缀和除以当前位置的个数”。因此写这题最优雅的思路是先维护一个累计变量 sum每遍历到一个新元素就把它加进去然后立刻计算 sum / (i 1)。注意下标从 0 开始所以第 i 个元素对应的个数是 i1这个细节我在初学的时候踩过坑后面会专门讲。有人可能会说那前缀和数组 pre 本身要不要存其实不需要。因为平均值只依赖当前累计总量不依赖历史的平均结果所以用一个变量 rolling sum 就够了。这种只用一个累计变量、边遍历边输出的写法既省内存又直观是这道题的标准解法。理解了这一点你再看 LeetCode 上类似的“Running Sum”题目会发现全是同一个套路。2. 从暴力到高效两种经典解法的完整推导2.1 暴力双层循环能跑但必须有代价认知先写暴力版本不是为了让你在正式答题时用它而是为了理解它为什么慢。代码很简单def prefix_average_brute(a): n len(a) res [] for i in range(n): total 0 for j in range(i 1): total a[j] res.append(total / (i 1)) return res内层循环每次都从 0 累加到 i所以第 i 次外层循环执行 i1 次加法。总加法次数是 1 2 ... n n(n1)/2时间复杂度 O(n^2)。空间复杂度除了答案数组外是 O(1)这是暴力法的唯一优点。为什么说它“能跑”因为当你拿它去刷题时如果 OJ 的测试数据只给到 n1000它确实能过但一旦 n 到 10^5Python 版本基本会在 2 秒左右超时C 版本也会明显变慢。我自己的实测记录是n10^5 的随机数组Python 暴力版跑了大约 11 秒C 暴力版跑了约 1.8 秒而优化版 Python 只跑了 0.02 秒。差距就是这么夸张。2.2 前缀和优化一次遍历解决战斗优化思路特别简单既然每次都要知道前 i 个元素的总和那我干脆用一个变量把它一直维护着来一个新元素就加一次这样每次算平均都是 O(1) 的操作。def prefix_average_fast(a): total 0 res [] for i, x in enumerate(a): total x res.append(total / (i 1)) return res这个版本的时间复杂度是 O(n)空间复杂度 O(n)答案数组必须返回。如果题目允许原地修改你甚至可以不用开 res直接把 a[i] 替换成平均值这样额外空间降到 O(1)。整体代码量不超过六行但背后是“累计变量代替重复求和”的核心思想。2.3 两种做法的复杂度对比与实测数据我特意整理了一张对比表方便大家直观感受差异方案时间复杂度空间复杂度n100n10^4n10^6暴力双层循环O(n^2)O(1)立即返回数百毫秒分钟级或超时前缀和单次遍历O(n)O(1) 或 O(n)立即返回毫秒级几十毫秒级这里的“O(1) 或 O(n)”取决于是否原地修改。如果要求返回新数组那 O(n) 是不可避免的如果允许直接覆盖原数组前缀和的原地版确实能做到额外空间 O(1)。我建议在实际工程中始终返回新数组因为覆盖原始数据容易引发副作用尤其在数据后续还要复用时。3. 流式场景下的递推平均比前缀和更进一步3.1 递推平均值的数学推导前缀和版本已经足够应付大多数 OJ 题目但如果你遇到的是“在线实时计算平均值”的场景——数据一个接一个到来你不能等全部收齐再算——那就需要另一种思路递推更新平均值。假设已经处理了前 i 个元素当前平均值是 avg_i现在来了第 i1 个元素 x。新的平均值可以这样推导总的和 avg_i × i x新的平均值 (avg_i × i x) / (i 1)写成代码就是avg 0 count 0 for x in stream: count 1 avg (avg * (count - 1) x) / count这个公式非常漂亮你不需要记住历史总和只需要保存当前平均值和当前个数来一个新数据就把旧平均值“换算”成旧总和加上新值再平分。很多实时监控系统、传感器数据聚合、在线评分系统用的都是这个思路。3.2 递推平均的典型应用场景在真实业务里前缀平均值最常见的使用场景是滚动统计。比如你想实时展示“当天到目前为止每笔订单的平均金额”每来一笔新订单你不可能把所有历史订单重新加一遍这时候递推平均公式就派上用场了。又比如流量监控系统要实时计算过去一段时间接口的平均响应时间如果数据是不断流进来的用前缀和思想按批次处理不如直接维护一个累计值和计数器的方案直观。还有一个场景是图像处理里的均值滤波器变体对图像每一行求前缀平均值可以快速得到某个像素之前所有像素的平均亮度用于实时调整曝光。虽然实际工程里多用积分图integral image实现二维区域求和但二维积分图的本质仍然是“先对每一维做前缀和”和这道题的底层逻辑完全一致。3.3 递推平均的数值稳定性隐患递推公式省内存但有一个隐藏问题当平均值特别大而当前值又特别小的时候avg * (count - 1) 可能会超出浮点数能精确表达的范围造成精度损失。举个例子如果当前已经处理了一百万个元素平均值是 10^6那么 avg × 999999 10^12 左右这个量级在 double 里没问题但如果平均值达到 10^15再乘以 10^6 就可能到 10^21double 的尾数精度就跟不上了。我自己在实测时遇到过这类问题用递推公式处理一组前几项特别大、后几项特别小的数据结果后面的平均值和暴力版本对不上误差达到 0.01 级别。解决方法是在数值动态范围很大的场景放弃递推公式老老实实维护一个高精度总和变量或者用 Python 的 decimal / fractions 模块。对于 OJ 题数据通常不会极端double 足够但要意识到这个坑。4. 多语言实现与边界处理4.1 参考代码Python、C、Java 三版本Python 版本我用两种写法都测试过简洁版最简单def prefix_average(nums): total 0 result [] for i, num in enumerate(nums): total num result.append(total / (i 1)) return resultC 版本要注意整数溢出问题。如果用 int 存总和n10^6 且每个元素在 10^4 量级时累积和直接爆掉 int 上限。标准写法用 long long 或 double#include vector using namespace std; vectordouble prefixAverage(const vectorint nums) { vectordouble res(nums.size()); long long total 0; for (int i 0; i nums.size(); i) { total nums[i]; res[i] static_castdouble(total) / (i 1); } return res; }Java 版本和 C 几乎一样累加器用 longpublic double[] prefixAverage(int[] nums) { double[] res new double[nums.length]; long total 0; for (int i 0; i nums.length; i) { total nums[i]; res[i] (double) total / (i 1); } return res; }三个版本的核心逻辑都只有四行但每一行都藏着细节类型选择、除法转换、下标偏移。4.2 边界条件与溢出陷阱边界条件至少要考虑四类空数组、单元素数组、全负数数组、整数除法坑。空数组直接返回空题目一般不会给空的测试点但健壮的代码应该先判空。单元素数组的答案就是它自身这一步能快速验证逻辑。全负数数组的平均值会是负数如果写成了“总和除以当前位置”而不是“除以 i1”结果就全错了。整数除法问题是 C 新手最容易踩的total 是 long longi1 是 int两者相除是整数除法必须先把 total 转成 double 再除。还有下标细节遍历到 i0 时对应的是第一个元素分母应该是 1也就是 i1。如果代码里写成 i第一个位置直接报了 ZeroDivisionErrorPython或除零异常C/Java。这个错误太常见了我在给初学者 review 代码时见过至少三次同样的错法。4.3 浮点精度问题什么时候能相信结果OJ 的浮点判定通常会允许 1e-6 左右的绝对误差所以普通 double 完全够用。如果你在本地用 float32 位实现碰上元素数量超过 10^5 或者元素值跨度很大误差可能累积到 0.1 以上大概率被判 Wrong Answer。记住口诀凡事涉及累加求和与除法优先 double只有内存极其紧张时才考虑 float而 OJ 题基本不会紧张到那个程度。还有一点不要用 Python 的 float 去做大量累加后再除这里虽然没问题但如果你把这套逻辑搬到统计每天交易总额、订单数很大的场景float 会慢慢积累误差。工程上更稳妥的做法是用 Decimal 或整数分单位存储比如把金额转成分从根源上规避浮点精度问题。5. 常见错误与调试实录5.1 最容易犯的三个错误第一重复初始化总和变量。有些人写暴力版时把 total 初始化在内层循环外导致每次内层循环越加越大平均值越算越离谱。正确做法内层每次从 0 开始累加或者在优化版里用一个变量在外层持续累加。这个错误的本质是“逻辑层次的混乱”。第二结果类型不对。题目要求输出浮点数平均值有人直接用整数除法导致 1 / 2 得到 0。这在 C 系语言里尤其隐蔽因为编译器不会报错你只会在答案比对时发现一片 Wrong Answer。第三原地覆盖导致后续数据丢失。我曾经图省事直接在原数组上更新平均值结果后续位置的累加用的是被覆盖后的值整个数组算出来全是错的。调试了半天才发现问题出在“还在用原数组的值”因为 a[i] 早就被改成平均值了。解决办法很简单先用一个变量存当前原始值再覆盖 a[i]。5.2 手算小样例的调试方法调试这类简单算法题最高效的方法是手算一个 5 元素样例。我一般用 [2, 4, 6, 8, 10]期望输出是 [2, 3, 4, 5, 6]。逻辑是第一个平均数是 2/12第二个是 (24)/23第三个是 (246)/34……如果代码输出和这个对不上基本就能确定是累加逻辑或分母的问题。再验证一下边界单元素数组 [7] 应该输出 [7.0]两个元素 [-3, 3] 应该输出 [-3.0, 0.0]。这两个小用例能同时验证负数处理和累加归零。把这些用例用一个简单的断言函数包起来每次改完代码跑一遍省得反复提交 OJ 浪费时间。5.3 对拍技巧让暴力版本当“裁判”如果你对自己的优化版本没有十足把握最稳妥的验证方式是写一个暴力版本作为基准然后用小规模随机数据对比两个版本的输出。这是我刷题时特别喜欢用的方法尤其是从 O(n^2) 优化到 O(n) 的时候可以快速确认结果是否一致。import random def brute(a): n len(a) return [sum(a[:i1]) / (i1) for i in range(n)] def fast(a): total 0 res [] for i, x in enumerate(a): total x res.append(total / (i 1)) return res for _ in range(1000): a [random.randint(-100, 100) for _ in range(random.randint(1, 20))] if abs(brute(a) - fast(a)).max() 1e-9: print(Mismatch:, a) break注意 Python 里 sum(a[:i1]) 是浮点运算和 fast 版本理论上要完全一致。这个对拍脚本能在几秒内跑几千组随机数据比肉眼自查可靠得多。6. 一点个人体会与扩展方向“10345 前缀平均值”这道题本身不难但它是前缀和、递推均值这两条路线的交汇点。我在实际刷题和工作中发现凡是涉及“前 i 项统计”的题目核心都是维护一个累计状态区别只在于状态是什么——是总和、最大值、最小值还是平均值。把这道题吃透后去看 LeetCode 的 724 题寻找数组的中心下标、303 题区域和检索、304 题二维区域和检索都会轻松很多因为它们全都是前缀和的变体。再说一个实际应用中的小技巧如果你需要同时输出“前缀平均值”和“当前最小值”完全可以在同一次遍历里维护两个变量一个累计总和、一个当前最小值不需要开两个循环。循环合并是常见的性能优化手段能少一次 O(n) 遍历就少一次尤其在处理几千万条数据时会明显感知到速度差异。最后我想说别因为这道题简单就跳过调试环节。我见过太多人写完代码直接提交、靠 OJ 的判题结果当调试器这种习惯在简单题上也许还行一旦遇到复杂题就会非常痛苦。我的习惯是先在本地用断言函数覆盖小样例再用暴力版随机对拍最后才提交。这个流程也许多花五分钟但能帮你省下十次无意义的 Wrong Answer 提交长期来看是最划算的刷题策略。