寻找使数组元素绝对差的c次幂之和最小的数值的算法

首先明确推导适用前提：幂次c ≥ 1，此时目标函数S(x) = Σ|a_i - x|^c为凸函数，存在全局最优解，不存在局部极小值干扰求解。

核心解析性质 #

对目标函数求导（c>1且x不等于数组中任意元素时可导），令导数为0可得最优值满足的条件：
c * Σ [ sign(x - a_i) * |x - a_i|^{c-1} ] = 0
整理后等价于：
Σ (x - a_i) * |x - a_i|^{c-2} = 0
代入常见参数即可对应已知结论：

• c=1时：导数符号由小于x的元素数量和大于x的元素数量的差值决定，导数为0等价于两侧元素数量相等，最优解为数组的中位数
• c=2时：导数简化为2*Σ(x - a_i) = 0，解得最优解为数组的平均值
• c→+∞时：最优解趋近于数组最大值与最小值的中点(max(A)+min(A))/2，此时目标等价于最小化最大绝对差

通用求解算法 #

所有c≥1的场景都可以用以下两种通用方法求解：

• 三分查找法：利用凸函数的单峰特性，在数组的最小值和最大值区间内做三分查找，迭代直到结果精度满足要求即可。时间复杂度为O(n * log((max(A)-min(A))/ε))，其中ε为设定的精度阈值，实现简单且稳定性高，适合所有场景。
• 迭代加权最小二乘法：以中位数或平均值作为初始值，每次迭代计算权重w_i = |x_k - a_i|^{c-2}，再更新x_{k+1} = (Σ w_i * a_i) / Σ w_i，反复迭代直到x的变化量小于精度阈值。收敛速度快于三分查找，适合c不接近1的场景。

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