1.前言
如果想知道我国的人口数量,就需要进行人口普查。让每一个省份都去统计本省有多少人, 然后将各省人口累加起来,就可以获得全国的人口数量。而要想知道某一个省的人口数量,可以 让省里的每一个城市统计本市有多少人,然后将各市人口累加起来,就可以获得这个省的人口数 量……以此类推,层层细分,最后统计一个村子或者一个小区有多少人,这个任务就很简单了。 把一个复杂的问题细分成若干结构相同但规模更小的子问题,然后将每个子问题的解合并起来, 就得到了复杂问题的解,就是本文将会介绍的分治策略。
2.分治算法详解
(I) 递归方程
分治算法建立在递归数学理论的基础上,其核心思想是将原问题分解为若干个相互独立且结构相似的子问题。从计算复杂度角度看,分治算法通常遵循特定的递归关系式。设T(n)T(n)T(n)表示解决规模为nnn的问题所需时间,则典型的分治递归式可表示为:
T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n)T(n)=aT(n/b)+f(n)
其中aaa表示子问题数量,n/bn/bn/b为子问题规模,f(n)f(n)f(n)是分解与合并的开销。
(II)主定理
所谓主定理,就是用来解递归方程的一种方法,此方法可以用来求解大多数递归方程。( 见(i) )
主定理:
以下是主定理(Master Theorem)三种情况的公式表示:
情况1:
f(n)=O(nlogba−ϵ) ⟹ T(n)=Θ(nlogba)f(n) = O(n^{\log_b a - \epsilon}) \implies T(n) = \Theta(n^{\log_b a}) f(n)=O(nlogb a−ϵ)⟹T(n)=Θ(nlogb a)
情况2:
f(n)=Θ(nlogba) ⟹ T(n)=Θ(nlogbalogn)f(n) = \Theta(n^{\log_b a}) \implies T(n) = \Theta(n^{\log_b a} \log n) f(n)=Θ(nlogb a)⟹T(n)=Θ(nlogb alogn)
情况3:
f(n)=Ω(nlogba+ϵ)且af(nb)≤cf(n) ⟹ T(n)=Θ(f(n))f(n) = \Omega(n^{\log_b a + \epsilon}) \quad \text{且} \quad a f\left(\frac{n}{b}\right) \leq c f(n) \implies T(n) = \Theta(f(n)) f(n)=Ω(nlogb a+ϵ)且af(bn )≤cf(n)⟹T(n)=Θ(f(n))
其中 (ϵ>0)(\epsilon > 0)(ϵ>0) 是常数,(c<1)(c < 1)(c<1) 是常数。
简洁版主定理
{Θ(nlogba)if f(n)=O(nlogba−ϵ)Θ(nlogbalogn)if f(n)=Θ(nlogba)Θ(f(n))if f(n)=Ω(nlogba+ϵ) 且 af(n/b)≤cf(n)\begin{cases} \Theta(n^{\log_b a}) & \text{if } f(n) = O(n^{\log_b a - \epsilon}) \\ \Theta(n^{\log_b a} \log n) & \text{if } f(n) = \Theta(n^{\log_b a}) \\ \Theta(f(n)) & \text{if } f(n) =
\Omega(n^{\log_b a + \epsilon}) \text{ 且 } a f(n/b) \leq c f(n) \end{cases} ⎩⎨⎧ Θ(nlogb a)Θ(nlogb alogn)Θ(f(n)) if f(n)=O(nlogb a−ϵ)if f(n)=Θ(nlogb a)if f(n)=Ω(nlogb a+ϵ) 且 af(n/b)≤cf(n)
其实这三条定理都是搞f(n)f(n)f(n)与logba\log_b alogb a的大小问题,但是相当**的是,我们可以发现,这个比大小很明显比的是多项式大小,所以就有可能看似这个比那个大但是在多项式意义上这个却不比那个大,这就相当坑爸爸了......
比如T(n)=2T(n2)+nlog2nT(n) = 2T\left(\frac{n}{2}\right) + n \log_2 nT(n)=2T(2n )+nlog2 n,这个式子很明显就相当坑爹,虽然f(n)=nlog2nf(n) = n \log_2 nf(n)=nlog2 n渐进大于nlogba=nn^{\log_b a} = nnlogb a=n,但是却不是多项式大于。这就是我纠结了很长时间。后来找到了一种证明
F(N)NLOGBA+Ε=NLOG2NN1+Ε=N−ΕLOG2N\FRAC{F(N)}{N^{\LOG_B A + \EPSILON}}=\FRAC{N \LOG_2 N}{N^{1+\EPSILON}} = N^{-\EPSILON} \LOG_2 NNLOGB A+ΕF(N) =N1+ΕNLOG2 N =N−ΕLOG2 N
,而对于任意正常数εεε,没有可能使其等于111,这至少我还算可以接受。
(III)总结
分治算法的效率很大程度上取决于子问题的划分方式和合并操作的复杂度。理想的划分应保持子问题规模均衡,且合并操作应尽可能高效。在实际应用中,还需要考虑递归调用的系统开销和边界条件的处理策略。
3.分治的应用
(I)归并排序
归并排序是分治策略的典型应用之一。它的基本思想是:将数组分成两半,递归地对每一半进行排序,然后将排序好的两半合并。
具体步骤如下:
分解:递归地将原数组(原问题)划分为两个子数组(子问题),直到子数组只剩一个元素(最小子问题)。
解决:每个子数组只有一个元素时,自然是有序的,因此不需要再排序。
合并:从底至顶地将有序的子数组(子问题的解)进行合并,从而得到有序的原数组(原问题的解)。
归并排序的时间复杂度为O(nlogn)O(n log n)O(nlogn),非常高效!
(II)快速排序
快速排序是另一种基于分治策略的排序算法。它的基本思想是:选取一个基准值,将数组分为小于基准和大于基准的两部分,然后递归地对这两部分进行排序。
具体步骤如下:
分解:选取一个基准值,将数组分成两部分,一部分包含所有小于基准的元素,另一部分包含所有大于基准的元素。
解决:递归地对这两部分进行排序。
合并:由于快速排序在分解的过程中已经实现了部分排序,因此不需要额外的合并步骤。排序完成后,整个数组就是有序的。
快速排序的平均时间复杂度也是O(nlogn)O(n log n)O(nlogn),但在最坏情况下会退化到O(n2)O(n^2)O(n2)。不过,由于它的实现简单且大多数情况下效率较高,因此在实际应用中非常受欢迎。
(III) 二分查找
二分查找是一种高效的查找算法,它适用于在有序数组中查找特定元素。二分查找也基于分治策略。
具体步骤如下:
分解:将有序数组从中点索引分为两部分。
解决:根据目标值与中间元素值的比较结果,决定排除哪一半区间,然后在剩余区间执行相同的二分操作。
合并:二分查找旨在查找一个特定元素,因此不需要将子问题的解进行合并。当子问题得到解决时,原问题也会同时得到解决。二分查找的时间复杂度为O(logn)O(log n)O(logn),非常高效!
(IIII) 矩阵乘法
矩阵乘法中的Strassen算法展示了分治策略如何突破传统复杂度界限。通过巧妙的子矩阵运算重组,它将888次乘法减少到777次,实现O(nlog27)≈O(n2.807)O(n^{log_2 7 }) ≈ O(n^{2.807})O(nlog2 7)≈O(n2.807)的复杂度。更先进的Coppersmith-Winograd算法进一步将指数降至约2.3762.3762.376,尽管实际应用受限。
4.分治的例题——快速幂
洛谷P1226
如果我们打算求aba^bab, 我们可能会写一个for循环,乘以bbb次aaa,时间复杂度为O(b)O(b)O(b)
当bbb比较小的时候还可以运用,但是当$b很大,此时时间复杂度就显然很高了,我们需要对其进行优化 ———快速幂
开始之前,先说两个前置知识:
1 二进制构成数字
众所周知,每个十进制数都可以由唯一的二进制数表示
我们不难发现,每一个十进制数都由其对应的二进制数,那么每一个十进制数都可以有$1 2 4 8 32 64 … $等这种二的次方数相加得到,并且每一种数只能取111个或000个
再例如 999,其二进制为100110011001 ,$ 8+1=9 $,即由111个888和111个111相加得到999
2 位运算
我们不难发现只有1&1才是1,根据这个思想,我们可以判断当前数字的二进制是否有1
其实不难发现,右移111就是除以222,>>n>>n>>n,就是除以2n2^n2n次方
结合&和>>
我们可以写个循环。逐渐判断每一位是否是111
3 快速幂算法(不取余版)
学完前面两个前置知识,我相信再学习 快速幂 将会很简单
首先假设我们要求5135^13513次方
131313的二进制为$1101 $所以13=8+4+113 = 8+4+113=8+4+1;
即513=51∗54∗585^{13} = 5^1 * 5^4 * 5^8513=51∗54∗58
ps: 幂运算可是初中数学学的 a(m+n)=am∗ana^{(m+n)}= a^m * a^na(m+n)=am∗an;
有这些知识我们就能直接看代码了
要是还有疑惑点,看代码注释也能看懂
4 取模版快速幂
快速幂只有五行代码,是不是很简单呢
不过别急,上面的快速幂是最原始版的,一般不是很常用,当aaa本身非常大时,如果a∗aa*aa∗a可能 long long 都给爆掉了,所以我们一般会采取取模的方式进行运算
前置知识 (a∗b∗c∗d)%p=(((a∗b)%p∗c)%p∗d)%p(a *b *c *d )\%p = (((a *b)\%p *c)\%p *d)\%p(a∗b∗c∗d)%p=(((a∗b)%p∗c)%p∗d)%p
即每次乘以下个数前可以先取模,这样最后答案不变,所以我们的代码可以进行优化了
5 完整代码
5.完结撒花
求置顶@AC君