分治算法求解n×n矩阵中的超级冠军查找问题

n名选手参加国际象棋锦标赛，每对选手之间都赛一场，结果用n×n矩阵A编码：

A[i,j] 的取值规则：
- 若i赢了j，值为i
- 若平局，值为0
- 若j赢了i，值为j

超级冠军的定义是：赢下了所有比赛（没平局、没输过）。现在要设计一个分治算法，输入矩阵A，存在超级冠军则返回其编号，否则返回0。要求时间复杂度O(n log n)，A可以当全局变量用，不用每次递归传。

已知条件：

• 选手之间只赛一次
• 矩阵对角线是0（自己不跟自己比）
• 矩阵对称
• 递归基例：只有1个选手时，他就是超级冠军

当前困惑：不知道怎么不用双重循环（会导致O(n²)复杂度）来验证候选的超级冠军。

核心思路 #

分治的关键是缩小孩子范围，而非挨个检查所有选手。因为超级冠军必须赢遍所有人，所以在任何子集中，真正的超级冠军必然是该子集的“全胜代表”——而且它必须赢过其他子集的代表。

递归流程 #

1. 基例处理：如果当前处理的选手子集只有1个人，直接返回他作为候选。
2. 拆分集合：把当前选手分成大小相近的两部分，比如左半组L和右半组R。
3. 递归求候选：分别对L和R递归处理，得到两个候选c_L和c_R。
4. 合并验证：
   • 如果两个候选都是0，说明当前组里没有超级冠军，返回0。
   • 如果只有一个候选非0（比如c_L不为0），检查这个候选是否赢了另一组的所有人。是则返回该候选，否则返回0。
   • 如果两个候选都非0，查看他俩的比赛结果：
     • 若A[c_L, c_R] == c_L，说明c_L赢了c_R——c_R不可能是超级冠军，只需验证c_L是否赢了R组所有人。验证通过返回c_L，否则返回0。
     • 若A[c_L, c_R] == c_R，反过来验证c_R是否赢了L组所有人，通过则返回，否则返回0。
     • 若结果为0（平局），两个候选都不符合要求，直接返回0。

候选验证方法 #

验证候选d是否赢了某组S的所有人，只需遍历S中每个选手x，检查A[d,x] == d即可。这一步的时间复杂度为O(k)，k是S的大小。

时间复杂度分析 #

设T(n)为处理n个选手的时间复杂度：

• 递归拆分公式：T(n) = 2*T(n/2) + O(n)
• 根据主定理，该递归式的解为T(n) = O(n log n)，符合要求。

比如n=4，选手编号0、1、2、3：

1. 拆分成{0,1}和{2,3}，递归得到c_L=0（0赢了1）、c_R=2（2赢了3）。
2. 查看A[0,2]，若值为0（0赢了2），接着检查A[0,3]是否为0——若是，说明0赢了所有人，返回0；若A[0,3]为3或0，则返回0。

• 超级冠军必须全胜，只要有一场平局或输局，直接排除候选资格。
• 合并阶段的验证只需针对另一组的选手，无需遍历整个集合——递归过程已保证候选在自己组内是全胜的。

内容的提问来源于stack exchange，提问作者Marc Delos