《算法第四版》课后练习题1.2.18答案

习题1.2.18

累加器的方差。以下代码为 Accumulator 类添加 var() 和 stddev() 方法，它们计算了 addDataValue() 方法的参数的方差和标准差，验证这段代码。

public class Accumulator
{
    private double m;
    private double s;
    private int N;
    public void addDataValue(double x)
    {
        N++;
        s = s + 1.0 * (N-1) / N * (x - m) * (x - m);
        m = m + (x - m) / N;
    }
    public double mean()
    {
        return m;
    }
    public double var()
    {  
        return s/(N - 1); 
    }
    public double stddev()
    {  
        return Math.sqrt(this.var());
    }
}

与直接对所有数据的平方求和的方法相比较，这种实现能够更好地避免四舍五入产生的误差。

要点分析

1.  累加器

累加器在课本的第57页。累加器定义了一种能够为用例计算一组数据的实时平均值的抽象数据类型。

2.  方差

方差简单来说就是，离平均的平方距离的平均[1]。这句话太难懂，于是我们可以举一个例子来告诉大家计算方差的步骤：

按照以下的步骤来计算方差：

• 求平均数
• 将每一个数值减去平均数得到一个差，然后平方。
• 将所有差的平方相加，再除以（N – 1），得到的值就是方差
  • 总体方差，除以N
  • 样本方差，除以N – 1

如果你还看不懂，这里给出两个图解方差的教程：

如何计算方差   标准差和方差

3.  标准差

标准差也被称为标准偏差，标准差(Standard Deviation)描述各数据偏离平均数的距离（离均差）的平均数，它是离差平方和平均后的方根，用σ表示。标准差是方差的算术平方根。也就是说，方差开根号就是标准差。标准差能反映一个数据集的离散程度，标准偏差越小，这些值偏离平均值就越少。

例如，A、B两组各有6位学生参加同一次语文测验，A组的分数为95、85、75、65、55、45，B组的分数为73、72、71、69、68、67。这两组的平均数都是70，但A组的标准差应该是18.708分,B组的标准差应该是2.366分，说明A组学生之间的差距要比B组学生之间的差距大得多。[2]

参考答案

import edu.princeton.cs.algs4.StdRandom;

public class Ex_1_2_18 {
    public static void main(String[] args) {
        Accumulator acu = new Accumulator();
        for (int i = 0; i < 1000; i++) {
            acu.addDataValue(StdRandom.random());
        }
        System.out.println(acu.var());
        System.out.println(acu.mean());
        System.out.println(acu.stddev());
    }

}

class Accumulator {
    private double m; // 平均数
    private double s; //样本方差* (n-1)
    private int N; //数据值数量
        
        //添加一个新的数据值
    public void addDataValue(double x) {
        N++;
        s = s + 1.0 * (N - 1) / N * (x - m) * (x - m);
        m = m + (x - m) / N;   //计算当前所有数字的平均值
    }
        
        //所有数据值的平均值
    public double mean() {
        return m;
    }

    //样本方差
    public double var() {
        return s / (N - 1);  
    }

    //标准差
    public double stddev() {
        return Math.sqrt(this.var());
    }
}

输出：
0.0843040982997624
0.48881826340510354
0.29035168038046966

参考资料

[1] 数学乐：标准差和方差​

[2] 百度百科：标准偏差