CMA滑动窗口均值算法的时间与空间复杂度计算确认

复杂度判断结论 #

• 你对空间复杂度的判断是正确的，时间复杂度的描述存在偏差，具体分析如下：

时间复杂度分析 #

你当前的描述混淆了单步操作耗时和全局算法复杂度：

1. 全局时间复杂度固定为O(n)：n为输入数组values的长度，整个算法只遍历输入数组一次，每一轮循环内的累加、除法、赋值操作都是常数级操作，总耗时和输入规模n成正比，不存在阶段变化。
2. 你提到的“达到窗口大小后变为O(1)”应该是指单步计算新平均值的耗时为常数级，这个判断是对的：和暴力实现的滑动窗口平均（每次重新遍历窗口内所有元素求和，单步耗时O(windowSize)）相比，你用累积变量sum缓存了和，不管窗口多大，单步计算都只需要常数时间。

空间复杂度分析 #

你的判断完全正确，空间复杂度为O(n)：

• 你创建了和输入数组等长的cValues数组存储所有位置的计算结果，占O(n)空间
• 额外用到的sum、count、i都是常数级临时变量，占O(1)空间
• 如果你不需要保留所有历史计算结果、只需要输出最新的平均值，空间可以优化到O(1)。

代码逻辑补充提示 #

顺便提一下你当前代码的潜在问题，不影响复杂度判断但会导致计算结果不符合预期：

1. 你当前的sum是累加所有历史输入值，没有在窗口满了之后减去滑出窗口的旧元素，当count >= windowSize之后，计算的是所有历史元素的总和除以windowSize，不是标准的滑动窗口平均结果。如果要实现标准滑动窗口平均，需要额外维护一个队列/数组存储窗口内的元素，每次加新值的同时减去最早移出窗口的元素。
2. 代码里的sum和count是方法外的全局变量，多次调用CMA方法时如果没有重新初始化，会导致结果错误。

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