分治法思考题

 一.求解a^n

1.问题描述：

采用分治策略来求解a^n。

2.问题分析：

（1）如果采用常规方法，n个a相乘，算法的复杂度是O(n)

（2）如果采用分治策略，算法的复杂度则可大大减少

a.当n为偶数时：a^n =(a^n/2) * a^n/2;
b.当n为奇数时：a^n = a^(n-1)/2 * a^(n-1)/2*a;
c.当n=1时： a^n=a;
此时复杂度减少为O(logn)

3.Code：

本题采用递归分治的方法进行求解。 

#include 
using namespace std;
typedef long long ll;
 
//递归求解（位运算会快一些）
ll fac(int a, int n){
	if (n == 1) return a;
	if (n & 1)//判断n是否为奇数
		return pow(fac(a, (n - 1) / 2), 2) * a;
	else 
		return pow(fac(a, n / 2), 2);
}
 
int main(){
	int a, n;
	while (~scanf("%d%d", &a, &n)) cout << "递归求解：" << fac(a, n) << endl;
	return 0;
}
 

4.代码运行截图：

5.拓展：

快速幂原理简述：

  

下面给出快速幂做法：

#include
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
 
ll quickmi(ll a, ll b){
	ll res = 1;
	while(b){
		if(b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;//左移，即b / 2。
	}
	return res;
}
int main(){
	int n,m;
	cin >> n >> m;
    cout << quickmi(n,m);
	return 0;
}

 二.求解第K小的数

1.问题描述：

给定一个长度为n的无序整数数列，以及一个整数k，求出数列从小到大排序后的第k个数（即求解第K小的数）。 

2.问题分析：

基于分治中快排的思想，从数组a[]中找出一个基准值v，把数组分为两部分a[l...j]和a[j+1...r]。a[l...j]中的元素小于v，a[j+1...r]中元素大于v。这时有两种情况：

a[l...j]中元素的个数大于等于k，则递归到数组a[l...j]中搜索的第k小的数。
a[l...j]中元素的个数小于k，则递归到数组a[j+1...r]中第k-(j-l+1)小的数
因为每次分区完只需要继续操作一边，所以该算法的平均时间复杂度是O ( n ) 

3.Code:

#include 
using namespace std;
const int N = 1e5 + 10;
int a[N];
 
int find(int l, int r, int k){
    if(l >= r) return a[l];//两指针相遇就返回
    
    int i = l - 1, j = r + 1;//防溢出
	int v = a[l + r >> 1];
    
    //把数组分为两部分a[l...j]和a[j + 1...r],其中a[l...j]中的元素小于v，a[j + 1...r]中元素大于v
    while(i < j){//由于内部的while遇到一次不满足的即停止，因此需要外面套一个大while保证整个过程的正常进行
        do i ++; while(a[i] < v);
        do j --; while(a[j] > v);
        if(i < j) swap(a[i], a[j]);
    }
    //选择区间后进行递归
    if(j - l + 1 >= k) return find(l, j, k);
    else return find(j + 1, r, k - (j - l + 1));
}
 
int main(){
    int n, k;
    cin >> n >> k;
    
    for(int i = 0; i < n; i ++) cin >> a[i];
    
    cout << find(0, n - 1, k) << endl;
    
    return 0;
}

ps：本题解巧妙之处：不同于两种朴素快排写法，对于快排的实现中i与j两指针可以交错，不影响功能的实现。 

4.代码运行截图：

 三.如何降低分治法的时间复杂度

1.分治中的平衡原则：一般情况下，子问题规模几乎相等时，分治法效率较高。

2.分治可进行二分，三分等等，具体怎么分，需看问题的性质和分治后的效果。只有认真分析分治后可能产生的预期效率，才能灵活地运用分治思想解决实际问题。        

3.在优化分治方面，通过减少子问题个数，减少子问题规模实现。 减少子问题个数意味着减少分治次数。减少子问题规模意味着提高每个子问题处理效率，均可降低分治法的时间复杂度。