3期望时间和平均时间的区别 令确定算法的平均执行时间 输入规模一定的所有输入实例是等概率出现时,算法 的平均执行时间。 令概率算法的期望执行时间 反复解同一个输入实例所花的平均执行时间。 因此,对概率算法可以讨论如下两种期望时间 ①平均的期望时间:所有输入实例上平均的期望执行时 间 ②最坏的期望时间:最坏的输入实例上的期望执行时间7 3. 期望时间和平均时间的区别 ❖ 确定算法的平均执行时间 输入规模一定的所有输入实例是等概率出现时，算法 的平均执行时间。 ❖ 概率算法的期望执行时间 反复解同一个输入实例所花的平均执行时间。 因此，对概率算法可以讨论如下两种期望时间 ① 平均的期望时间：所有输入实例上平均的期望执行时 间 ② 最坏的期望时间：最坏的输入实例上的期望执行时间