#创作计划# 分治算法分析
2025-07-20 12:35:53
发布于：浙江
1.前言
如果想知道我国的人口数量，就需要进行人口普查。让每一个省份都去统计本省有多少人， 然后将各省人口累加起来，就可以获得全国的人口数量。而要想知道某一个省的人口数量，可以 让省里的每一个城市统计本市有多少人，然后将各市人口累加起来，就可以获得这个省的人口数 量……以此类推，层层细分，最后统计一个村子或者一个小区有多少人，这个任务就很简单了。 把一个复杂的问题细分成若干结构相同但规模更小的子问题，然后将每个子问题的解合并起来， 就得到了复杂问题的解，就是本文将会介绍的分治策略。
2.分治算法详解
(i) 递归方程
分治算法建立在递归数学理论的基础上，其核心思想是将原问题分解为若干个相互独立且结构相似的子问题。从计算复杂度角度看，分治算法通常遵循特定的递归关系式。设表示解决规模为的问题所需时间，则典型的分治递归式可表示为：
其中表示子问题数量，为子问题规模，是分解与合并的开销。
(ii)主定理
所谓主定理，就是用来解递归方程的一种方法，此方法可以用来求解大多数递归方程。（ 见(i) ）
主定理：
以下是主定理（Master Theorem）三种情况的公式表示：
情况1：
情况2：
情况3：
其中 是常数， 是常数。
简洁版主定理
其实这三条定理都是搞与的大小问题，但是相当**的是，我们可以发现，这个比大小很明显比的是多项式大小，所以就有可能看似这个比那个大但是在多项式意义上这个却不比那个大，这就相当坑爸爸了......
比如，这个式子很明显就相当坑爹，虽然渐进大于，但是却不是多项式大于。这就是我纠结了很长时间。后来找到了一种证明
，而对于任意正常数，没有可能使其等于，这至少我还算可以接受。
(iii)总结
分治算法的效率很大程度上取决于子问题的划分方式和合并操作的复杂度。理想的划分应保持子问题规模均衡，且合并操作应尽可能高效。在实际应用中，还需要考虑递归调用的系统开销和边界条件的处理策略。
3.分治的应用
(i)归并排序
归并排序是分治策略的典型应用之一。它的基本思想是：将数组分成两半，递归地对每一半进行排序，然后将排序好的两半合并。
具体步骤如下：
分解：递归地将原数组（原问题）划分为两个子数组（子问题），直到子数组只剩一个元素（最小子问题）。
解决：每个子数组只有一个元素时，自然是有序的，因此不需要再排序。
合并：从底至顶地将有序的子数组（子问题的解）进行合并，从而得到有序的原数组（原问题的解）。
归并排序的时间复杂度为，非常高效！
(ii)快速排序
快速排序是另一种基于分治策略的排序算法。它的基本思想是：选取一个基准值，将数组分为小于基准和大于基准的两部分，然后递归地对这两部分进行排序。
具体步骤如下：
分解：选取一个基准值，将数组分成两部分，一部分包含所有小于基准的元素，另一部分包含所有大于基准的元素。
解决：递归地对这两部分进行排序。
合并：由于快速排序在分解的过程中已经实现了部分排序，因此不需要额外的合并步骤。排序完成后，整个数组就是有序的。
快速排序的平均时间复杂度也是，但在最坏情况下会退化到。不过，由于它的实现简单且大多数情况下效率较高，因此在实际应用中非常受欢迎。
(iii) 二分查找
二分查找是一种高效的查找算法，它适用于在有序数组中查找特定元素。二分查找也基于分治策略。
具体步骤如下：
分解：将有序数组从中点索引分为两部分。
解决：根据目标值与中间元素值的比较结果，决定排除哪一半区间，然后在剩余区间执行相同的二分操作。
合并：二分查找旨在查找一个特定元素，因此不需要将子问题的解进行合并。当子问题得到解决时，原问题也会同时得到解决。二分查找的时间复杂度为，非常高效！
(iiii) 矩阵乘法
矩阵乘法中的Strassen算法展示了分治策略如何突破传统复杂度界限。通过巧妙的子矩阵运算重组，它将次乘法减少到次，实现的复杂度。更先进的Coppersmith-Winograd算法进一步将指数降至约，尽管实际应用受限。
4.分治的例题——快速幂
洛谷P1226
如果我们打算求, 我们可能会写一个for循环，乘以次，时间复杂度为
当比较小的时候还可以运用，但是当$b很大，此时时间复杂度就显然很高了，我们需要对其进行优化 ———快速幂
开始之前，先说两个前置知识：
1 二进制构成数字
众所周知，每个十进制数都可以由唯一的二进制数表示
例如：13的 二进制表示为 1101 即表示为 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0
即13可以由8+4+1组成
我们不难发现，每一个十进制数都由其对应的二进制数，那么每一个十进制数都可以有$1 2 4 8 32 64 … $等这种二的次方数相加得到，并且每一种数只能取个或个
再例如 ，其二进制为 ，$ 8+1=9 $，即由个和个相加得到
2 位运算
& 运算符可以直接对二进制进行操作，1 & 1 = 1，1 & 0 =0， 0 & 1 = 0， 0 & 0 = 0，
我们不难发现只有1&1才是1，根据这个思想，我们可以判断当前数字的二进制是否有1
>> 右移运算符，可以删掉末尾二进制数
例如5 的二进制为101 5>>1 ==2 2的二进制为10 删掉了原先末尾的1
再例如6的二进制为110 6>>1==3 3的二进制为11 删掉了末尾的0
其实不难发现，右移就是除以，,就是除以次方
结合&和>>
我们可以写个循环。逐渐判断每一位是否是
int b = 13;
int res = 0;//统计b二进制1的数目
while(b){
if(b&1==1)res++; //如果当前位为1，就统计+1
b = b>>1;//将末尾位删掉
}
3 快速幂算法(不取余版)
学完前面两个前置知识，我相信再学习 快速幂 将会很简单
首先假设我们要求次方
的二进制为$1101 $所以；
即
ps: 幂运算可是初中数学学的 ;
有这些知识我们就能直接看代码了
要是还有疑惑点，看代码注释也能看懂
long long quick_pow(long long a,long long b){
//计算a^b次方
long long res = 1;//用res保存答案
//当b变成0后就可以停止循环了
while(b){
if(b & 1) ans*=a;//如果b当前二进制为1就要乘上这个数
b>>=1; //将b末尾的二进制数删掉
a*=a; // 将a乘以自己进行翻倍
//比如，开始a==5,接下来a = 5^2,a=5^4,a=5^8,a=5^16....
//通过遍历每个在范围内的2的次方数来更新a
}
}
4 取模版快速幂
快速幂只有五行代码，是不是很简单呢
不过别急，上面的快速幂是最原始版的，一般不是很常用，当本身非常大时，如果可能 long long 都给爆掉了，所以我们一般会采取取模的方式进行运算
前置知识
即每次乘以下个数前可以先取模，这样最后答案不变，所以我们的代码可以进行优化了
LL quick_pow(LL a, LL b, LL p){ //LL是long long 的缩写
//p是要对取模的数字
LL ans = 1;
while(b){
if(b & 1)ans =(ans*a)%p;
b >>= 1;
a = (a*a) % p;
}
return ans;
}
5 完整代码
#include<iostream>
using namespace std;
typedef long long LL;
LL n;
LL quick_pow(LL a, LL b, LL p){
LL ans = 1;
while(b){
if(b & 1)ans =(ans*a)%p;
b >>= 1;
a = (a*a) % p;
}
return ans;
}
int main(){
cin>>n;
while(n--){
LL a,b,p;
cin>>a>>b>>p;
cout<<quick_pow(a,b,p)<<endl;
}
return 0;
}
5.完结撒花
求置顶@AC君
有帮助，赞一个