算法博弈与分治：优势策略均衡与中位数求解

算法考试1主要考察了两个核心概念：优势策略均衡与纳什均衡，以及分治算法的应用，特别是解决排序数组中位数的问题。 **优势策略均衡（Dominant Strategy Equilibrium, DSE）** 优势策略均衡是一种博弈理论中的策略选择原则，其中每个参与者无论对方采取何种策略，都能选择对自己最有利的策略。这种均衡状态确保了即使对手的策略未知，每个玩家仍能维持最佳决策。例如在囚徒困境中，每个囚犯都知道独自坦白比保持沉默更有利于自己，这就是优势策略。然而，优势策略均衡并不总是存在，且它属于纳什均衡的一种特殊情况，即当一个策略对所有可能的对手策略都是最优时，才会形成优势策略均衡。 **纳什均衡（Nash Equilibrium, NE）** 纳什均衡则是针对非合作博弈的情况，每个参与者在给定其他所有参与者的策略前提下，选择对自己最优的策略。在这种状态下，没有任何一方有动力改变自己的策略，因为无论对方怎么做，他们的选择都是最佳的。如智猪博弈中的例子，大猪和小猪各自选择吃食或等待，达到一种平衡状态。纳什均衡强调了策略的互动性和动态性，而优势策略均衡则是纳什均衡的一种特例，意味着在纳什均衡中至少有一个策略是优势策略。 **分治算法（Divide and Conquer）在寻找中位数问题上的应用** 题目要求设计一个在两个已排序数组`X[0:n-1]`和`Y[0:n-1]`中查找2n个数的中位数，时间复杂度为O(logn)。分治算法的关键在于将问题分解为规模较小的子问题。首先，分别找到两个数组的中位数`x0`和`y0`，然后根据两者大小关系缩小搜索范围。如果`x0`等于`y0`，则直接返回结果；若`x0`小于`y0`，中位数可能在`X[x0,n-1]`或`Y[0,y0]`内，反之亦然。接着，递归地对这两个子数组重复上述过程，直到找到中位数为止。这个算法利用了排序数组的特性，通过二分查找的思想，在每次划分后都能有效地缩小搜索空间，从而达到O(logn)的时间复杂度。 本篇考题涵盖了博弈论中的策略选择理论和数据结构与算法的实用应用，重点在于理解并运用这些概念解决实际问题。考生需要掌握优势策略均衡与纳什均衡的区别，以及如何设计高效的分治算法来求解特定问题。