中科大概率算法课件：随机选择的效率

数字算法课程是中国科学技术大学计算机系教授黄刘生在2008年8月19日为学生准备的一门课程，着重讲解概率算法的应用。在课程中，通过一个富有启发性的神化故事，阐述了概率算法如何在面对复杂问题时发挥作用。 故事中，主人公面对一张难以理解的地图，有两个可能的藏宝地点，但确定哪个更准确需要花费时间，而此时面临恶龙每晚偷窃宝藏的威胁。在这个情境下，两个方案被提出： 1. **确定算法**：通过4天计算出确切位置，然后花费5天寻找，最后可能得到的价值为 x - 9y，但考虑到时间成本和风险，这个方案可能不如其他两种灵活。 2. **小精灵帮助**：接受小精灵的帮助，付出3晚的被盗财宝作为代价，虽然可能损失一部分，但总的得到值为 x - 8y，这个方案在不考虑冒险的情况下更为经济。 3. **随机选择（冒险方案）**：通过掷硬币决定先后顺序，一次成功可得 x - 5y，机会1/2；二次成功 x - 10y，机会1/2。这种随机策略的期望赢利为 x - 7.5y，有时可能优于精心计算。 这个故事的核心概念是，当最优解的成本过高，且随机选择的平均收益可以超过最优情况时，概率算法可以提供一种更有效的方法。它强调了概率算法的优势在于期望时间，而非最坏情况下的表现。在实际应用中，如快速排序中的随机划分，学生们被鼓励写出算法，即使在简单划分可能会导致较高运行时间的情况下，也要考虑随机化策略以提高效率。 课程内容还包括对期望时间和平均时间的区分，确定算法的平均执行时间是指所有等概率出现的输入实例，而概率算法的期望执行时间则是在同一输入实例上重复运行的平均时间。课程还介绍了两种类型的期望时间：平均的期望时间和最坏的期望时间，以全面评估算法性能。 这门课程不仅介绍了概率算法的基本原理，还通过实际案例展示了其在解决实际问题中的优势和适用场景，让学生们理解在面临复杂决策时，如何权衡算法的效率和不确定性。