算法设计与问题求解

算法与问题求解的基本概念

算法：是解决问题的方法或过程，严格地讲是满足下述性质的指令序列：

输入：有零个或多个外部量作为算法的输入；
输出：算法产生至少一个量作为输出；
确定性：组成算法的每条指令清晰、无歧义
有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限。

程序：是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(4)即有限性。

“玩具”问题

计数：判断一个byte（无符号整数）里面有多少个bit的值为1？

int Cal(uchar iValue){
	uchar iCount = 0;
	while(iValue != 0){
		iReminder = iValue%2;
		if(iReminder == 1)
			iCount++;
		iValue = iValue/2;
	}
	return iCount;
}

如果这个子函数需要调用很多次，内存空间足够，怎样提高性能？

对于这样的一个场景，我们可以采取打表的方法，也就是说，我们提前把所有的无符号整数里面有多少个bit值为1的答案算出来，保存在一个数组里面，因为所有的无符号整数总共有256个，它们是指0,1,...,255，毫无疑问，我们从数组中直接寻找答案比调用上述程序的效率会更高一些

int iTables[256] = {...};
iCount = iTables[iValue];

如果既想省时间，又想省空间，怎样改进？

在这样的一个场景下，我们可以应用一个数据结构——哈希表，在应用这个数据结构的时候，如果我们要去求iValue的答案，我们先到哈希表里去找，如果说在哈希表里面有iValue的答案，我们直接返回它的结果；如果在哈希表里面没有现成的答案，我们再去调用上述的算法，这样的话使得我们能达到既省时间，又相对省空间的目的。

HashMap Maps;
if(Maps.containsKey(iValue)){
	Count = Maps.get(iValue)}
else{
	Maps.put(Value.new Interger(Cal(iValue)))}

总之，在我们设计算法的时候，时间和空间是我们需要重点考虑的两个因素，可以说它是我们度量一个算法的两个重要的标杆

连续子序列和

问题描述：给定一个整数数组{A1,A2,...,An}，连续子序列和定义为：
(subSum(i,j) = A_i+A_{i+1}+...+A_{j-1}+A_j)
试求解输入数组的连续子序列和的最大值。如果所有的整数都是负数，那么最大连续子数列和为0。
例如：

{1,-3,4,5}的最大子数列为{4,5}，因为4+5最大为9
{3,4,-5,8,-4}的最大子数列为{3,4,-5,8}，因为3+4-5+8最大为10
{4,3,-1,2}的最大子数列为{4,3,-1,2}，因为4+3-1+2最大为8

算法1：三层循环

int maxSubSum1(const vector<int> &a)
{
	int maxSum = 0;
	for(int i=0;i<a.size();i++)
		for(int j=i;j<a.size();j++)
		{
			int thisSum = 0;
			for(int k=i;k<=j;k++)
				thisSum+=a[k];
			if(thisSum>maxSum)
				maxSum = thisSum;
		}
	return maxSum;
}

其中第三层for循环(thisSum(i,j)=A_1+...+A_{j-1}+A_j)可以写成一个递推的公式(thisSum(i,j)=thisSum(i,j-1)+A_j)，就可以把最里层的for循环消除掉，写成两层循环

算法2：二层循环

int maxSubSum2(const vector<int> &a)
{
	int maxSum = 0;
	for(int i=0;i<a.size();i++)
	{
		int subSum = 0;
		for(int j=i;j<a.size();j++)
		{
			subSum+=a[j];
			if(subSum>maxSum)
				maxSum = subSum;
		}
	}
	return maxSum;
}

我们也可以应用最优子结构的性质，把两成循环的算法改造为一层循环的算法

当j=1时 b[j] = max(a[1],0)
当j>1时 b[j] = max(b[j-1]+a[j],0)

算法3：一层循环

int maxSubSum3(const vector<int> &a)
{
	int maxSum = 0,bj = 0;
	for(int j=0;j<a.size();j++)
	{
		bj+=a[j];
		if(bj>maxSum)//记录最优值
			maxSum = bj;
		else if(bj<0)
			bj = 0;
	}
	return maxSum;
}

算法4：递归方法

int maxSumRec(const vector<int> &a, int left, int right)
{
	if(left == right)	//Base case
		if(a[left]>0)
			return a[left];
		else
			return 0;

	int center = (left+right)/2;
	int maxLeftSum = maxSumRec(a, left, center);
	int maxRightSum = maxSumRec(a, center+1, right);
	
	int maxLeftBorderSum = 0, leftBorderSum = 0;
	for(int i = center;i>=left;i--)
	{
		leftBorderSum+=a[i];
		if(leftBorderSum>maxLeftBorderSum)
			maxLeftBorderSum = leftBorderSum;
	}
	
	int maxRightBorderSum = 0, rightBorderSum = 0;
	for(int j = center+1;j<=right;j++)
	{
		rightBorderSum+=a[j];
		if(rightBorderSum>maxRightBorderSum)
			maxRightBorderSum = rightBorderSum;
	}

	return max(max(maxLeftSum,maxRightSum),maxLeftBorderSum+maxRightBorderSum);//三者最大
}

四种算法的效率比较

算法规模	三层循环	二层循环	一层循环	递归方法
100	<1ms	<1ms	<1ms	<1ms
1000	<4s	<10ms	<1ms	<1ms
100,000	>60h	>30m	<1ms	<1s