Yao's Minimax Principle 一个随机算法的最坏运行时间，是它在所有输入实例中期望运行时间的最大值 试考虑这样的一个零和游戏： “算法”玩家需要从不同的算法中选择，目标是最小化运行时间 “攻击”玩家需要从不同的输入实例中选择，目标是最大化运行时间 “算法”的混合策略：随机算法 “攻击”的混合策略：输入实例的概率分布 要成功地“攻击”所有的随机算法，等价的问题是： 给出一个输入实例的概率分布，使得所有的确定性算法的期望运行时间都比较大 8Yao’s Minimax Principle 一个随机算法的最坏运行时间，是它在所有输入实例中期望运行时间的最大值 试考虑这样的一个零和游戏： “算法”玩家需要从不同的算法中选择，目标是最小化运行时间 “攻击”玩家需要从不同的输入实例中选择，目标是最大化运行时间 “算法”的混合策略：随机算法 “攻击”的混合策略：输入实例的概率分布 要成功地“攻击”所有的随机算法，等价的问题是： 给出一个输入实例的概率分布，使得所有的确定性算法的期望运行时间都比较大 8