5.1.2 Probabilistic analysis 概率分析:使用关于输入分布的知识或者对其做的假 设,然后分析算法,计算出一个期望的运行时间。 实际上是将所有可能输入的运行时间做平均。 确定输入的分布时必须非常小心。 有些问题,对所有可能的输入集合可以做某种假 定,也可以将概率分析作为一种手段来设计高效 算法,并加深对问题的认识。 有些问题可能无法描述一个合理的输入分布,则 不能用概率分析方法。5.1.2 Propbabilistic analysis ➢ 概率分析：使用关于输入分布的知识或者对其做的假 设，然后分析算法，计算出一个期望的运行时间。 ➢ 实际上是将所有可能输入的运行时间做平均。 ➢ 确定输入的分布时必须非常小心。 • 有些问题，对所有可能的输入集合可以做某种假 定，也可以将概率分析作为一种手段来设计高效 算法，并加深对问题的认识。 • 有些问题可能无法描述一个合理的输入分布，则 不能用概率分析方法