中科大算法设计与分析.docx

Edit by James Wu 2011/1/10 概率算法部分 1.0几个基本概念 1.0.1 期望时间和平均时间的区别 确定算法的平均执行时间输入规模一定的所右输入实例是等概率出现时, 算法的平均执行时间 概率算法的期望执行时间反复解同一个输入实例所花的平均执行时间 概率算法的平均期望时间所有输入实例上平均的期望执行时间 概率算法的最坏期望时间最坏的输入实例上的期望执行时间 1.0.2 Un