排序不等式
2020-08-31 08:46:42
排序不等式是数学上的一条不等式。它可以推导出很多有名的不等式,例如算术几何平均不等式(简称算几不等式),柯西不等式,和切比雪夫总和不等式。它是说:
如果
是两组实数。而
是
的一个排列。排序不等式指出以文字可以说成是顺序和不小于乱序和,乱序和不小于逆序和。与很多不等式不同,排序不等式不需限定
的符号。排序不等式可以用数学归纳法证明。关键在于下列结果:
若
,则有移项得出
重复以上步骤便可得出排序不等式。
我们设Si为b1,b2,...bn 原序列 的前i个数的和,即Si=b1+b2+...bi;设S' 为打乱顺序后的序列,S'i表示乱序后的前i个数的和。所以有:Si<=S'i. 注意到 a-a<=0 则 Si*(a-a)>=S'i*(a-a)
得证