概率算法与期望效率：科大课程讲解

"这是一份来自中国科技大学黄刘生老师的概率算法课程课件，适合考博、考研者或自学算法的人员参考。课程主要讲解概率算法的设计与分析，通过一个寻宝的故事引入了概率算法的概念，探讨在面对选择时，随机决策可能优于最优决策的情况。" 在这份课件中，黄刘生老师首先介绍了算法设计与分析的基础，特别是在概率算法领域的应用。他以一个生动的寻宝故事为例，展示了在不确定性和风险存在的环境下，如何利用概率算法来做出决策。故事中，有两个可能的藏宝地点，每个地点的价值用x表示，恶龙每晚会盗走一部分宝藏，价值为y。面临两种方案：一是花4天时间确定准确位置，二是付给小精灵3y作为报酬获取信息，再用5天时间寻宝。 在比较这两种方案时，引入了概率算法的预期收益概念。通过计算，发现如果允许冒险，即随机选择一个地点并根据结果调整策略，那么预期收益可以达到x-7.5y，这高于确定性方案的收益。这个例子揭示了概率算法的一个关键特点：在某些情况下，即使存在失败的风险，随机策略的平均效率可能超过确定性的最优策略。 接着，课件讨论了概率算法的期望时间和平均时间的差异。确定算法的平均执行时间是指所有等概率出现的输入实例下的平均时间，而概率算法的期望执行时间则涉及在单一输入实例上反复执行的平均时间。这里区分了两种期望时间：一是所有输入实例上的平均期望时间，二是最坏输入实例上的期望执行时间。 课件还提到了快速排序中的随机划分问题，这是一个经典的概率算法应用实例，它展示了在实际编程竞赛或评分环境中，随机化策略可能带来的优势，因为它们在大多数情况下都能提供良好的性能，而不是只依赖于最坏情况的表现。 这份课件深入浅出地介绍了概率算法的基本思想和应用，对于理解和掌握这一领域有着极大的帮助，无论是对于学术研究还是实际问题解决，都能提供宝贵的理论支持和启发。