滑动窗口绝对中位差（MAD）高效算法及近似算法探究

问题描述 #

滑动窗口在数组X上滑动时，需要为每个窗口计算对应的绝对中位差（MAD）。目前计算滑动中位数可通过有序列表等结构实现高效处理，但计算MAD时，每一步窗口中位数变化后，所有元素的偏差都要重新计算，暴力算法复杂度至少为O(窗口大小 × 数组长度)。想知道是否存在更高效的通用算法？如果没有，有没有精度较好的近似算法？

暴力实现示例 #

以下是暴力计算的Python代码，仅作演示参考：

import numpy as np

def median(data):
    return np.median(data)

def median_absolute_deviation(data):
    m = median(data)
    abs_deviation = [abs(x - m) for x in data]
    return median(abs_deviation)

def rolling_mad(data, window_size):
    result = []
    for i in range(len(data) - window_size + 1):
        window = data[i:i + window_size]
        result.append(median_absolute_deviation(window))
    return result

data = [10, 12, 11, 120, 14, 13, 15, 300, 18, 19]
rolling_mad_result = rolling_mad(data, window_size=4)
print(rolling_mad_result)

解答 #

精确高效算法的可能性 #

目前没有已知的通用精确高效算法能将Rolling MAD的时间复杂度降到O(n log k)级别（k为窗口大小，n为数组长度），核心原因在于：

• MAD的计算依赖两个步骤：先求窗口中位数m，再求所有元素与m的绝对偏差的中位数。
• 滑动窗口时，m的变化会导致所有绝对偏差值改变，而这些偏差值的集合无法像原始窗口元素那样通过增量更新的有序结构（如双堆、平衡二叉搜索树）维护——每个偏差值都和当前窗口的强绑定，中位数一变，所有偏差都要重新计算，无法复用之前的偏差数据。

也就是说，要精确计算每个窗口的MAD，理论上无法避免对窗口内元素进行至少一次遍历计算偏差，时间复杂度下限接近O(nk)，除非针对特定数据分布（如整数、有限值域）做优化，但这类优化不具备通用性。

精度较好的近似算法 #

如果可以接受一定的精度损失，以下几种近似方案可大幅降低时间复杂度：

• 基于滑动标准差的近似估计：对于正态分布数据，MAD ≈ 0.6745 × 标准差。可以通过维护窗口的和、平方和实现O(1)更新滑动标准差，再乘以系数得到MAD近似值。复杂度O(n)，但仅在数据接近正态分布时精度较高。
• 采样近似法：对每个窗口随机采样一部分元素，用采样集的MAD近似整个窗口的MAD。滑动时保留上一个窗口的部分采样，替换移出元素的采样，复杂度O(n × s)（s为采样大小，远小于k），通用性强，可根据需求平衡速度与精度。
• 分桶近似法：将数据值域划分为多个桶，维护窗口内每个桶的元素计数。滑动时更新桶计数，先通过桶快速估算窗口中位数m，再统计偏差的桶分布来估算偏差的中位数。复杂度O(n × b)（b为桶数量，远小于k），适合值域有限的场景，桶越多精度越高。

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