算法性能分析（以最大子序列计算为例子）

算法（性能）分析

1 数学基础

定义：

①如果存在正常数c和 $n_0$n0​ 使得当 $N\ge n_0$N≥n0​ 时 $T\left(N\right)\le cf\left(N\right)$T(N)≤cf(N) ,则记为 $T\left(N\right)=O\left(f\right(N\left)\right)$T(N)=O(f(N)) .

②当 $T\left(N\right)=O\left(f\right(N\left)\right)$T(N)=O(f(N)) 时，可以保证函数 $T\left(N\right)$T(N) 是在以不快于 $f\left(N\right)$f(N) 的速度增长，因此 $f\left(N\right)$f(N) 是 $T\left(N\right)$T(N) 的一个上界。很明显“大O”与“小o”的意思完全不同，“小o”表示的是等价无穷小，前者只是表示一个上界。

③ $lo{g}^{2}N=O\left(N\right)$log2N=O(N) ,这说明对数增长非常缓慢，一般而言： $c\&lt;logN\&lt;lo{g}^{2}N\&lt;N\&lt;NlogN\&lt;N^2\&lt;N^3\&lt;2^N$c<logN<log2N<N<NlogN<N2<N3<2N (分别对应常数、对数、对数平方、线性的、线性对数、二次的、三次的、指数的)。

2 要分析的问题

通常只考虑平均情形 和最坏情形 ，考虑最优情形是没有意义的。平均情形反应典型的场景，而最坏情形反应对于任何输入的一种可能的保证。一般而言，都要保证最坏的情形。

3 一般法则

①一个for循环的复杂度一般是 $O\left(N\right)$O(N) 的

②递归的时间复杂度一般是指数级别的

③使用分治和递归 可以最大限度的发挥递归的效果，同时显著降低时间复杂度。一般而言对于二分的分治加递归，时间复杂度是 $O\left(NlogN\right)$O(NlogN) 。计算公式： $T\left(N\right)=cT\left(N/2\right)+N$T(N)=cT(N/2)+N

④如果一个算法用常数时间 $O\left(1\right)$O(1) 将问题的大小削减为一部分（通常是1/2），那么该算法的时间复杂度就是 $O\left(logN\right)$O(logN) 。

4 实际例子

最典型的是这个例子：最大子序列问题
描述：整数A1，A2，… ，An，求 ${\sum }_{i=1}^j{A}_k$∑i=1j​Ak​ 的最大值。

解答：

①穷举法，时间复杂度 $O\left(N^3\right)$O(N3)

public static int maxSubSum(int [] a){
	int maxSum = 0;
	for (int i = 0; i < a.length; i++) {
		for (int j = i; j < a.length; j++) {
			int tempSum = 0;
			for (int k = i; k < j; k++) {
				tempSum += a[k];
			}
			if (tempSum > maxSum) {
				maxSum = tempSum;
			}
		}
	}
	return maxSum;
}

②穷举法，时间复杂度 $O\left(N^2\right)$O(N2)

public static int maxSubSum(int [] a){
	int maxSum = 0;
	for (int i = 0; i < a.length; i++) {
        int tempSum = 0;
		for (int j = i; j < a.length; j++) {
			tempSum += a[k];
			if (tempSum > maxSum) {
				maxSum = tempSum;
			}
		}
	}
	return maxSum;
}

③分治法（使用递归），时间复杂度 $O\left(NlogN\right)$O(NlogN)

publci static int max3(int a, int b, int c){
    if (a > b && a > c)
        return a;
    else if (b > a && b > c)
        return b;
    else
        return c;
}
public static int maxSubRec(int [] a, int left, int right){
	if (left == right) {
		if (a[left] > 0) {
			return a[left];
		}
		else{
			return 0;
		}
	}
	int center = (left + right)/2;
	int maxLeftSum = maxSubRec(int []  a, left, center);
	int maxRightSum = maxSubRec(int [] a, center + 1, right);
	int maxLeftBorderSum = 0; leftBorderSum = 0;
	int maxRightBorderSum = 0; rightBorderSum = 0;
	for (int i = center; i >= left; i-- ){
		leftBorderSum += a[i];
		if (maxLeftBorderSum < leftBorderSum){
			maxLeftBorderSum = leftBorderSum;
		}
	}
	for (int j = center; i <= right; i++){
		rightBorderSum += a[i];
		if (maxRightBorderSum < rightBorderSum){
			maxRightBorderSum = rightBorderSum;
		}
	}
	return max3(maxLeftSum,maxRightSum,
				maxLeftBorderSum + maxRightBorderSum);
}
public static int maxSubSum(int [] a) {
	return maxSumRec(int [] a, 0, a.length);
}

④扫描法，时间复杂度 $O\left(N\right)$O(N)

思路是：一直扫描相加，总和为负就换序列。

public int maxSubSum(int [] a){
	int maxSum = 0; temp = 0;
	for (int i = 0; i < a.length; i++){
		temp += a[i];
		if (temp > maxSum) {
			maxSum = temp;
		}else if (temp < 0){
			temp = 0;
		}
	}
	return maxSum;
}