上一篇文章学习了【算法设计与分析】14 分治算法的一般描述和分析方法

本篇文章借助具体的例子来学习分治策略。这个例子是课本上的：芯片测试的例子。

在讲解具体的芯片测试的分治策略算法之前，先来了芯片测试的意思

如上图，A、B为芯片。测试方法为：将2片芯片（A和B）置于测试台上，互相进行测试，测试报告是“好”或者“坏”，只取其一。

那么上述测试的结果有四种可能,如下图:

上面的结果应该不难理解

那么现在问题来了:

针对上述问题，现在先来研究一下，如何在上述n片芯片中，测试出A是好芯片还是坏芯片？

假设：n=7:好芯片数>=4

所以对于n是奇数情况下：好芯片数>=（n+1）/2 A好，至少有(n-1)/2个报“好” A坏，至少有(n+1)/2个报“坏”

结论：

假设: n=8:好芯片数>=5

所以对于n是偶数：好芯片数 >= n/2+1. A 好, 至少有 n/2个报告“好” A 坏, 至少有 n/2+1个报告“坏”

结论：n-1份报告中

上面的分析，已经很清晰，我们已经知道如何测试一块芯片的好坏。那么人们最拿手的方法就是：暴力算法（蛮力算法）可以直接写代码了。。。

测试算法：任取 1片测试，如果是好芯片，测试结束；如果是坏芯片，抛弃，再从剩下芯片中任取 1片测试，直到得到 1片好芯片

时间估计：

第一片是坏芯片，最多测试n-2次 第二片是坏芯片，最多测试n-3次 …

总计： Θ ( n 2 ) \Theta(n^2) Θ(n2)

可见时间复杂度之高，数据量一多，肯定会超时。

在分析分治算法的正确性之前，我们先给出这个算法的描述：

假设n为偶数，将n片芯片两两一组做测试淘汰，剩下芯片构成子问题，进入下一轮分组淘汰。

淘汰规则为：

递归截止条件：n 2k+j

得出：i>k

所以，剩余的芯片好芯片比坏芯片，至少多1片。命题1 是正确的。即证明了上述分治算法的正确性。

当n为奇数时，特殊处理。当n是奇数时，可能会出现问题，如图： 可见淘汰后的子问题并不满足于原问题性质相同，此时无法继续测试。

下面给出上述分治算法的伪码描述：

设输入规模为n，，每轮淘汰后，芯片数至少减半，测试次数（含轮空处理）：O(n)

时间复杂度：

W(n) = W(n/2) + O(n) W(3)=1,W(2)=W(1)=0

解上述方程的得：W(n) = O(n)

结果很振奋人心，你已经将一个 O ( n 2 ) O(n^2) O(n2)级别的算法优化为了 O ( n ) O(n) O(n)级别!!!

最大的需要注意的地方就是：如何保证子问题与原问题性质相同:

可以：