algorithm-递归与分治策略

！！复习算法考试所用，代码为老师课堂手写，逻辑没错，应该有点小问题，需要修改才能运行，仅供思路参考

递归

递归：自身调用自身

定义：直接或间接的调用自身的算法称为递归算法，用函数自身给定出定义的函数称为递归函数
如线性查找

int find(T *a,int l,int r,const T &x)//其实也就是从0依次往后找，emmm强行递归
{
	//在a[l]....a[r] 查找x
	if(r<l)  return -1;
	if(l==r&&a[l]==x)
	{
		return l;
	}
	else {
		return -1;
	}
	int m = (l+r)/2;
	//区间分为l,...m 和 m+1....r
	int r1 = find(a,l,m,x);
	if(r1>=0) return r1;
	else{
		return find(a,m+1,r.x);
	}
}

同时求最值

template<class T>
T getMax(T *a,int l,int r)
	{//求a[l].....a[r]的最大值
		if(l==r)
			return a[l];
		int m = ( l + r ) / 2;
		//注：当r>l时，m>=l,m<r
		T m1 = getMax(a,l,m);
		T m2 = getMax(a,m+1,r);
		return m1>m2?m1:m2;
	}

分析：

T(n) = 0 n=1

T(n) = 2T(n/2)+1 = 2^k* T(1) + 2^(k-1) + 2^(k-2)...+1 = n-1 (k = log2(n)) n>1

同时求最大最小值

注:stl中有pair

相当于

template<class T1,class T2>
struct pair
{
	T1 first;
	T2 second;
}

分治求最大及最小

template<class T>
pair<T,T> minMax(T *a,int l,int r)
{
	//即求a[l]...a[r]的最大值及最小值
	pair<T,T> v;
	if(l==r)
	{
		v.first = a[l];
		v.second = a[l];
		return v;
	}
	//下面是 l<r
	int m = (r+l)/2;
	pair<T,T> v1 = minMax(a,l,m);
	pair<T,T> v2 = minMax(a,m+1,r);
	v.first = v1.first<v2.first?v1.first:v2.first;
	v.second = v1.second<v2.second?v2.second:v1.second;
	return v;
	}

分析：

T(n) = o n<=1;

T(n) = aT(n/2)+2 n>1

递归贼多

总工作量 T(n) = 2+ 2* 2 + 2^2* 2 +.....2^k* T(1)

fibonacci 数列

Fn = 1 n = 0,1

Fn = Fn-2+Fn-1 n>1

不能直接采用递归方法，否则会有大量重复运算

ex:求树高

	template<class T>
	struct Node{
		T data;
		Node<T> *l,*r;
	}
	//树高为层数
	template<class T>
	int getH(Node<T> *t)
	{
		if(t==NULL)//空树高为0
		{
			return 0;
		}
		Node<T> *lt = t->l;
		Node<T> *rt = t->r;
		int lh = getH(lt);
		int rh = getH(rt);
		int maxH = lh>rh?lh:rh;
		return (maxh+1);
	}

分治策略

分治策略的基本思想 : 问题->分解->分解....->归并

Divide_and_conquer(P){
	if(|p|<=n0)  //规模足够小
	{
		y = 非递归方法求解p
		return y;
	}
	//分解 p 到 p1,p2,p3.....;
	for(int i = 1;i<=k;i++)
	{
		yi = Divide_and_conquer(pi);
	}
	y = Merge(y1....yk);
	return y;
}

分析（递归方程）

T(n) = C(常量) n<=n0

T(n) = k* T(n/m) + f(n) n>n0

注 :

n/m 为子问题的规模
k 为子问题个数
f(n) = D(n) + M(n）分别为分解工作量和合并工作量
f(n) = θ(n^d) 或 f(n) = O(n^d) 即分解+合并工作量为多项式级别

如：同时求最大最小问题中

T(n) = 2 * T(n/2)+( 0 + 2 ) 分别为分解（仅作(l+r)/2,无比较）,比较（两次元素比较）

归并排序

a[0].......a[n-1]

计算中间下标：m = (l+r )/2 无比较，即D(n) = 0

归并合并工作量

Mmax(n) = n - 1
Mmin(n) = n/2

归并排序

Tmin(n) = 0 n<=1

Tmin(n) = 2 * Tmin(n/2) + n/2 n>1

Tmax(n) = 0 n<=1

Tmax(n) = 2 * Tmax(n/2) + n-1 n>1

或者

T(n) = 0 n<=1
T(n) = 2* T(n/2) + O(n) n>1

快速排序

最坏： T(n) = n*(n-1)/2
最好： T(n) = 2 * T(n/2) + (n-1) = θ(nlogn)

密码学中

如计算 x^64 mod 65537, x^1024 mod 65537,
且注意到 x^2048 = x^1024* x^1024

T(n) = 0 n =1
T(n) = 2* T(n/2)+1 n为偶数
T(n) = T(n-1)+1 n为奇数

x^n = x^(n/2)* x^(n/2) n为偶数

x^n = x^(n-1)* x n为奇数

最有效非递归模重复平方算法

主定理

设T（n）= C n =1

设T（n）= k*T(n/m) + θ（n^{d）（θ（n}d） = D(n)+M(n) 或 O(n^d) 为多项式级别）

k>=1 , m>=1

存在

T(n) = θ(n^d) d>logm(k)
T(n) = θ(n^d*logn) d=logm(k)
T(n) = θ(n^(logm(k))) d<logm(k)

如T(n) = 2T(n/2) + θ(n)
此处 k = 2 ,m = 2 , d =1 =>d=logm(k) =>T(n) = θ(n^d* logn) = θ(n* logn)

二分查找（最坏情况）

T(n) = T(n/2)+1
此处 k =1, m = 2 , d =0 =>d = logm(k) => T(n) = θ(logn)

同时求最大最小

T(n) = 2* (T/2) + 2;
=>k = 2,m = 2,d = 0 d<log2(2) =>θ(n)

求解递归方程

方法一：直接展开

对于 f(n) = θ(n^d)
T(n) = n^d + (k/(m^d))* n^d +......(k/(m^d))(l-1)* n^d.....

注：1+r+r^2+.....rl

r<1 上式极限为常数
r=1 上式为l
r>1 相当于 r^(l+1)

方法二：运用主定理

当 k = m^d 即 d = logm(k)
=>T(n) = l* n^d + O(n^(logm(k))) = (logm(n))* n^d + θ(n^d) =(logm(n)+1)* n^d = θ(logn* n^d)

当 k < m^d 即 d > logm(k)
=>T(n) = θ(n^d)

当 k > m^d 即 d < logm(k)
=>T(n) = θ(n^logm(k))

heihei12305

algorithm-递归与分治策略

algorithm-算法复杂度相关