决策树与下界分析

最近看到了几个有趣的利用决策树等相关技巧分析一些问题复杂度下界的例子,感觉非常有意思,特别是其中一些问题不仅给出了一个紧的下界,甚至还给出了达到下界的算法,所以想在这里整理一下。

Coin Weighing

你有\(n\)枚硬币和一架天平,天平没有配套的砝码,游码也坏掉了。硬币外观和重量本应一模一样,但其中有一枚假币比其它硬币都轻。现在需要设计一个方案把假币找出来,并最小化天平使用次数。

结论:天平使用次数不少于\(\left\lceil\log_3n\right\rceil\)

证明:考虑决策树,每次使用天平会出现三种情况:左边较重、右边较重和两边一样重,故决策树上每个点有三个儿子。由于哪枚硬币是假币是未知的,所以至少有\(n\)种情况,每种情况对应决策树上一个节点。假设决策树高度为\(h\),则需满足不等式\(3^h\geq n\),解得\(h\geq\left\lceil\log_3n\right\rceil\),结论得证。

Coin Weighing 2

你有\(n\)枚硬币和一架天平,天平没有配套的砝码,游码也坏掉了。硬币外观和重量本应一模一样,但其中有一枚假币和其它硬币重量不同。现在需要设计一个方案把假币找出来,并最小化天平使用次数。

结论:天平使用次数不少于\(\left\lceil\log_3{(2n+1)}\right\rceil\)

证明:由于哪枚硬币是假币是未知的,且假币比真币轻还是重也是未知的,所以看上去至少有\(2n\)种情况,但这里有一个例外:有可能天平两端一直平衡,最终我们也能找到假币,但此时无法判断其偏轻或偏重,所以一共有\(2n-1\)种情况,故\(h\geq\left\lceil\log_3{(2n-1)}\right\rceil\),但这个结论还不够紧,我们做进一步考虑。

为了证明给出的结论,我们来证明\(h\)次称量不能找出\(\frac{3^h+1}{2}\)枚硬币中的假币即可,考虑决策树的根节点,显然每次称量天平两侧的硬币数应相同,假设根节点天平的两侧各有\(c\)个硬币,接下来分为两种情况:

①天平不平衡,则假币在这\(2c\)个硬币中,此时最终一定能够判断出假币偏轻还是偏重,情况与第一个问题相同,故决策树高至少为\(\left\lceil\log_3{2c}\right\rceil\)。

②天平平衡,则假币在剩下\(n-2c\)个硬币中,这是这个问题的一个子问题,我们知道此时决策树高至少为\(\left\lceil\log_3{(2(n-2c)-1)}\right\rceil\)。

现在我们有两个不等式:

$$h\geq\left\lceil\log_3{2c}\right\rceil$$

$$h\geq\left\lceil\log_3{(2(n-2c)-1)}\right\rceil$$

代入\(n=\frac{3^h+1}{2}\),可得\(c\)有唯一解\(\frac{3^{h-1}}{2}\),但这不是一个整数,故根节点不存在一个可行的方案使得\(h\)次称量能找出\(\frac{3^h+1}{2}\)枚硬币中的假币,但是\(h+1\)次称量可以与上同理给出一个可行方案,故\(\left\lceil\log_3{(2n+1)}\right\rceil\)是一个紧的下界,结论得证。

Sorting

求解基于比较的排序的复杂度下界。

结论:复杂度下界为\(\Omega(nlogn)\)

证明:考虑决策树,每次比较有两种结果,\(n\)个数可能的大小关系有\(n!\)种,设决策树的高度为\(h\),则有\(2^h\geq n!\),解得\(h\geq\Omega(nlogn)\),结论得证。

Second Largest Number

设计一个方案从\(n\)个数中找出次大数,并最小化比较次数。

结论:最少进行\(n+\left\lceil\log_2n\right\rceil-2\)次比较。

证明:如果找到了次大数,那么在这之前一定以及找到了最大数,否则无法确定所找的数为次大数。

考虑决策树,最大数有\(n\)种情况,之后问题变成了在剩下\(n-1\)个数中找到最大数,这个子问题需要比较\(n-2\)次,设决策树的高度为\(h\),则有\(2^h\geq n\cdot2^{n-2}\),解得\(h\geq n+\left\lceil\log_2n\right\rceil-2\),结论得证。

Medium Number

设计一个方案从\(n\)个数中找出中位数,并最小化比较次数。

结论:最少进行\(1.5n\)次比较。

证明:找到中位数之后,这\(n\)个数将被分为三部分:中位数\(x_{mid}\),小于中位数的数的集合\(L\)和大于中位数的数的集合\(R\),其中由中位数的定义有\(|R|=\frac{n}{2}\)。

集合\(R\)有\(C^{n/2}_n\)种情形,然后问题等价于在\(\begin{Bmatrix}x_{mid}\end{Bmatrix}\cup L\)中找到最大数,考虑决策树,设决策树的高度为\(h\),则有\(2^h\geq2^{\frac{n}{2}-1}\cdot C^{n/2}_n=2^{\frac{n}{2}-1}\cdot\frac{n!}{(\frac{n}{2})!\cdot(\frac{n}{2})!}\),为了方便计算,用Stirling公式\(n!\approx\sqrt{2\pi n}\cdot(\frac{n}{e})^n\)做一步近似,得\(2^h\geq\sqrt\frac{2}{\pi n}\cdot2^{\frac{3n}{2}-1}\),解得\(h\geq1.5n-1+\frac{1}{2}\log_2\frac{2}{\pi n}\approx1.5n\),结论得证。

发表评论

电子邮件地址不会被公开。 必填项已用*标注