1.二分查找


有序队列 a[0],a[1],a[2],....a[n]

注：可以重载一个"<",来表示其他的

  • a<b : a<b
  • a>b : a>b
  • a==b : !(a< b)&&!(b<a)
  • a<=b : !(b<a)

设a[-]的类型是T,有"<"

template<class T>
int bisearch(T *a,int l,int r,const T &v)
{
	if(r<l)
		return -1;
	//l<=r
	int m = ( r + l ) / 2
	if(v<a[m])
	{
		return bisearch(a,l,m-1,v);
	}
	if(a[m]>v)
	{
		return bisearch(a,m+1,r,v);
	}
	return m;
}

算法分析：

分+归并：工作量为0

最好情况：1次比较

最坏情况：O(logn)


2.大整数乘法

分治：ab = a1 b1* 10^n+(a1* b2+a2* b1)* 10^(n/2)+a2* b2
T(n) = 4T(n/2) = = n^2(没改进)

令 p = a1b1 , q = a2 b2 , r = (a1 + a2)* (b1 * b2)
a * b = p*10^n + ( r - p - q)*10^(n/2) + q
T(n) = 3T(n/2) = n(log2(3))<n2

补：二分查找的应用问题

struct TStudent
{
	int id;
	int age;
	string name;
};
//由于bisearch中有"<",故必须对TStudent重载"<"
bool operator(const Tstudent & x,Tstudent & y)
{
	//按id进行比较
	return x.id<y.id;
}
int n = 50000;
TStudent *a = new TStudent[n];
for(int i = 0;i<n;i++)
{
		a[i].id = ...;
		a[i].new = ...;
		a[]....
}
std::sort(a,0,n);
TStudent v = new int TStudent();
int pos = biSearch(a,0,n-1,v);
.....
delete[] a;//释放内存

3.大矩阵乘法


分治平均:

  • C11 = A11B11+A12B21
  • .....
  • C22 =A21B12+A22B22

乘法-》P(n) = 8 P(n/2) = n^3
加法-》A(n) = 8A(n/2)+n^2

如何改进？

可改进， 改进后 7次n/2次矩阵乘法，但是加法次数增多