什么是算法的Average-Case Analysis'? 算法的性能依赖于输入数据的随机性 口“好”数据、“差”数据、“不好不差”数据 ■3 完全可以围绕“算法的性能”定义输入数据集（样本空间)上的随机变量 ■算法的平均开销就是这个随机变量的“平均” 口这个随机变量的“期望” We focus on computing the running time of various algorithms. When the running time of an algorithm is different for different inputs of the same size,we can think of the running time of the algorithm as a random variable on the sample space of inputs,and thus,we can analyze the expected running time of the algorithm.This gives us an understanding different from studying just the worst-case running time for an input of a given size.什么是算法的Average-Case Analysis? ◼ 算法的性能依赖于输入数据的随机性 ❑ “好”数据、“差”数据、“不好不差”数据 ◼ 完全可以围绕“算法的性能”定义输入数据集（样本空间）上的随机变量 ◼ 算法的平均开销就是这个随机变量的“平均” ❑ 这个随机变量的“期望