@fyywy520
2016-06-15T12:39:45.000000Z
字数 7904
阅读 8584
数据结构
算法
java
使用递归计算诸如裴波那切数列之类简单的数学函数的值的想法一般来说并不是一个好主意,其道理正是根据第四条法则。(后面将会介绍)
解决的主要问题:
函数 | 名称 |
---|---|
常数 | |
对数 | |
对数平方的 | |
线性的 | |
二次的 | |
三次的 | |
指数的 |
典型的情形是,输入的大小是主要的考虑方面。我们定义两个函数和,分别为算法对于输入量所花费的平均运行时间和最坏情况的运行时间。
这里是计算的一个简单的程序片段:
public static int sum(int n) {
int partialSum;
partialSum = 0;
for(int i = 1; i <= n; i ++)
partialSum += i * i * i;
return partialSum;
}
分析如下:
第4行和第8行各占1个时间单位。 第6行每次执行占用4个时间单位(2个乘法、1个加法、1个赋值),而执行次共占用个时间单位。
第5行初始化时占用1个时间单位,所有测试为个时间单位,自增运算为个时间单位。
忽略调用方法和返回值的开销,得到的总量是个时间单位,因此,我们说该方法是的。
为了简化以上的分析工作,可以利用如下若干一般法则。
一个for
循环的运行时间至多是该for
循环内部那些语句(包括测试)的运行时间乘以迭代次数。
从里向外分析这些循环,内部语句的总的执运行时间等于语句的运行时间乘以所有for
循环大小的乘积。
例如,下列程序片段为
for(i = 0; i < n; i ++){
for( j = 0; j < n; j ++)
k ++;
}
加和即可,也即各语句的最大值就是运行时间。
对于程序片段
if( cond )
S1
else
S2
一个if/else
语句的运行时间从不超过判断的运S1
和S2
中运行时间长者的总的运行时间。
分析的基本策略是从内部(或最深层的部分)向外展开的。如果有方法调用,首先要分析方法调用。如果有递归过程,则需要看其是否只是for
循环的变形,如下程序只是一个简单的循环从而其运行时间是:
public static long factorial(int n) {
if(n <= 1)
return 1;
else
return n * factorial(n-1);
}
当递归正常调用时,将其转换成为一个for
循环是相当困难的,这样的情况下分析将涉及求解一个递推关系,例如下面的程序:
public static long fib(int n) {
if(n <= 1)
return 1;
else
return fib(n-1) + fib(n-2);
}
对于,有下列关于fib(n)
的运行时间公式:
这个程序之所以运行缓慢,是因为其存在了大量的多余工作要做,违反了合成效益法则。试想,fib(3)
调用了fib(2)
和fib(1)
,而fib(4)
又调用了fib(3)
和fib(2)
,如此下去其中被抛弃的信息量合成起来导致了大量的运行时间。所以,「计算任何事情不要超过一次」。
给定(可能有负的)整数,求的最大值。(为方便起见,如果所有整数均为负数,则最大子序列的和为负数0)
例如:对于输入-2,11,-4,13,-5,-2,答案为20(从到)。
对于这个问题我们将讨论求解的四种算法,它们的性能如下:
输入大小 | 算法时间 | |||
1 |
2 |
3 |
4 |
|
N=10 | 0.000 009 | 0.000 004 | 0.000 006 | 0.000 003 |
N=100 | 0.002 580 | 0.000 109 | 0.000 045 | 0.000 006 |
N=1 000 | 2.281 013 | 0.010 203 | 0.000 485 | 0.000 031 |
N=10 000 | NA | 1.232 9 | 0.005 712 | 0.000 317 |
N=100 000 | NA | 135 | 0.064 618 | 0.003 206 |
不难看出,对于小量的输入,这些算法都在眨眼之间完成,因此如果只是小量输入的情形,那么花费大量的努力去设计聪明的算法恐怕就太不值得了。另一方面,进来对于重写那些不再合理的基于小输入量假设而在五年前变西欧的程序确实存在巨大的市场。对于大量的输入,算法4显然是最好的选择。
/**
* Cubic maximum contiguous subsequence sum algorithm.
*/
public static int maxSubSum1(int[] a) {
int maxSum = 0;
for (int i = 0; i < a.length; i++) {
for (int j = i; j < a.length; j++) {
int thisSum = 0;
for (int k = i; k <= j; k++) {
thisSum += a[k];
}
if (thisSum > maxSum) {
maxSum = thisSum;
}
}
}
return maxSum;
}
该算法只是穷举所有的可能,易证明,该算法主要为第12行的加等运算在深度为三级的循环中执行的运算。
事实上:
我们可以通过撤除一个for
循环来避免三次的运行时间,也就是说算法一中11行和12行的计算是过分消耗了的,改进后的算法如下:
/**
* Quadratic maximum contiguous subsequence sum algorithm.
*/
public static int maxSubSum2(int[] a) {
int maxSum = 0;
for (int i = 0; i < a.length; i++) {
int thisSum = 0;
for (int j = i; j < a.length; j++) {
thisSum += a[j];
if ( thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
算法二显然是的,其分析比算法一还简单。
算法三采用一种「分治(divide-and-conquer)」策略。其想法是把问题分成两个大致相等的子问题,然后递归地对他们求解,这是「分」的部分。「治」阶段将两个子问题的解修补到一起并可能再做些少量的附加工作,最后得到整个问题的解。
在这个例子中,最大子序列可能出现在三处,整个数据的左半部、右半部或者横跨中间。前两种情况可以直接递归求解,第三种情况可以通过求解左半部分的右侧最大序列和以及右半部分的左侧最大序列和而得到。
考虑如下输入:
前半部分 | 后半部分 | ||||||
4 | -3 | 5 | -2 | -1 | 2 | 6 | -2 |
其前半部分的最大子序列和为6(到)而后半部分的最大子序列和为8(到)。
前半部分的右侧最大序列和为4(到),而后半部分的左侧最大序列和为7(到)。因此,横跨这两部分的最大和为(到)。
故而此例中,最大子序列和就是11。
下面是该算法的一种实现手段:
/**
* Recursive maximum contiguous subsequence sum algorithm.
* Finds maximum sum in subarray spanning a[left..right].
* Does not attempt to maintain actual best sequence.
*/
private static int maxSumRec(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(s, center, 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 i = center; i <= right; i++) {
rightBorderSum += a[i];
if (rightBorderSum > maxRightBorderSum)
maxRightBorderSum = rightBorderSum;
}
return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum)
}
/**
* Driver for divide-and-conquer maximum contiguous
* subsequence sum algorithm.
*/
public static int maxSubSum3(int[] a) {
return maxSumRec(a, 0, a.length);
}
程序解析:
递归调用的一般形式是传递输入数组以及左边界和右边界,它们界定数组要被处理的部分。单行驱动程序通过传递数组以及边界0
和N-1
而将递归过程启动。
程序的第7到12行描述了一种基准情况,第15和16行调用两个递归过程,第18到23和第25到30行分别给出了到达中间分界处的两个和数的最大值,max3
(未定义)给出了算法中三个部分的最大值。
通过递归过程的调用,我们不难看出:
经过推导,也可知。
若非算法四给出了一个线性时间运行的解法,这个算法就会使体现递归为例的极好的范例了。
我们不妨这样来理解最大序列和的问题:如果子序列由一个负数a[i]
开头,那么这个子序列的和必然不能是最大的,因为a[i+1]
开头的子序列必然更大,所以i
可以推进到i+1
。推广一下,如果a[i]
到a[j]
的子序列和是负数,那么包含这个子序列的序列和也不可能是最大的,因此直接把i
推进到j+1
是没有风险的:我们的最优解也不会错过。
/**
* Linear-time maximum contiguous subsequence sum algorithm.
*/
public static int maxSubSum4(int[] a) {
int maxSum = 0, thisSum = 0;
for (int j = 0; j < a.length; j++) {
thisSum += a[j];
if (thisSum > maxSum)
maxSum = thisSum;
else if (thisSum < 0)
thisSum = 0
}
return maxSum;
}
这个算法是许多聪明算法的典型:运行时间是显而易见的,但正确性则不那么容易看出来。
该算法附带的一个优点是,它只对数据进行一次扫描,一旦数组被读入并处理,就不再需要被记忆。不仅如此,在任意时刻,算法都能对他已经读入的数据给出子序列问题的正确答案(其他算法不具备这个特性)。具有这种特性的叫做联机算法(on-line algorithm)。
仅需要常量空间并以线性时间运行的联机算法几乎是完美的算法!
分析算法最混乱的地方就是在对数上面,某些分治算法将以运行。此外,对数最常出现的规律可以概括为下列一般法则:
如果一个算法用常数时间将问题的大小削减为其一部分(通常是1/2),那么该算法就是。另一方面,如果使用常数时间只是把问题减少一个一个常数的数量(如将问题减少1),那么这种算法就是的。
通常我们计算这些算法时都假设输入数据已经提前读入。
给定一个整数和整数,后者已经预先排序并在内存中,求下标使得,如果不在序列中,则返回-1
。
最明显的解法是从头到尾扫描数据,其运行时间是线性的。然而这个算法并没有利用到序列已经排序的事实。一个好的策略应该是判断是不是居中的元素,如果是则返回,如果大于居中的元素,则在左半部分中继续寻找,如果小于居中的元素,则在右半部分中继续寻找:
/**
* Performs the standard binary search.
* @return index where item is found, or -1 if not found.
*/
public static <AnyType extends Comparable<? super AnyType>>
int binarySearch(AnyType[] a, AnyType x) {
int low = 0, high = a.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid].compareTo(x) < 0)
low = mid + 1;
else if (a[mid].compareTo(x) > 0)
high = mid - 1;
else
return mid;
}
return NOT_FOUND; //NOT_FOUND is defined as -1
}
上述程序中每次迭代所有工作花费的时间,因此需要分析循环次数。循环是从high
-low
开始并在high
-low
时结束,每次循环后,high
-low
的值至少会折半,因此不难看出,程序的运行时间是。
第二个例子是计算最大公因数的欧几里得算法。两个整数的最大公因数()是同时整除二者的最大整数。于是,:
public static long gcd(long m, long n) {
while (n != 0) {
long rem = m % n;
m = n;
n = rem;
}
return m;
}
算法连续计算余数直到余数是0为止,最后的非零余数就是最大公因数。因此如果m
=1989和n
=1590,则余数序列是399,393,6,3,0,从而。
可以证明,在两次迭代后,余数最多是原数值的一半,所以迭代次数至多是。
事实上,欧几里得算法在平均情况下的性能需要大量篇幅的高复杂度数学分析,其迭代的平均次数约为。
最后一个例子是处理一个整数的幂。计算的明显算法是进行次乘法自乘。有一种递归算法效果更好。是基准情形。否则,若是偶数则,若是奇数则。
显然,所需要的乘法次数最多是:
public static long pow(long x, int n) {
if (n == 0)
return 1;
if (n == 1)
return x;
if (isEven(n))
return pow(x * x, n / 2);
else
return pow(x * x, n / 2) * x;
}
其实上述程序有很多可以调整之处,例如第4行和第5行可以不必要,第9行也可以改写成:
return pow(x, n - 1) * x;
但如果把第7行改为:
return pow(x, n / 2) * pow(x, n / 2);
则会使得程序的效率下降因为此时有两个的递归调用而不是一个,其运行时间将不再是。
一旦分析过后,就要想办法检验分析是否正确,常用的办法是编程来实际观察到运行时间,一般来说,当扩大一倍时:
单凭纯时间区分线性程序还是是有一定难度的。
至此,我们已经通过实例了解了如何简单地对算法的复杂性进行分析。