数据结构与算法基础1()

1、
2、
3、
4、
5、
6、

01算法复杂度

大O记号

同样地出于保守的估计,我们首先关注T(n)的渐进上界。为此可引入所谓“大O记号”(big-O notation) 。
具体地,若存在正的常数c和函数f(n),使得对任何n >> 2都有
T(n) <= c∙f(n)则可认为在n足够大之后, f(n)给出了T(n)增长速度的一个渐进上界。此时,记之为:
T(n) = O(f(n))
由这一定义,可导出大O记号的以下性质:
(1) 对于任一常数c > 0,有O(f(n)) = O(c∙f(n))
(2) 对于任意常数a > b > 0,有O(n^a + n^b) = O(n^a)

大Ω记号

为了对算法的复杂度最好情况做出估计,需要借助另一个记号。如果存在正的常数c和函数g(n),使得对于任何n >> 2都有T(n)  c∙g(n)
就可以认为,在n足够大之后, g(n)给出了T(n)的一个渐进下界。此时,我们记之为:
T(n) = Ω(g(n))
这里的Ω称作“大Ω记号” (big-Ω notation)。
与大O记号恰好相反,大Ω记号是对算法执行效率的乐观估计—对于规模为n的任意输入,算法的运行时间都不低于Ω(g(n))。比如,即便在最好情况下,起泡排序也至少需要T(n) = Ω(n)的计算时间。

大Θ记号

借助大O记号、大Ω记号,可以对算法的时间复杂度作出定量的界定,亦即,从渐进的趋势
看, T(n)介于Ω(g(n))与O(f(n))之间。若恰巧出现g(n) = f(n)的情况,则可以使用另一记号来表示。
如果存在正的常数c1 < c2和函数h(n),使得对于任何n >> 2都有
c1∙h(n) <= T(n) <= c2∙h(n)
就可以认为在n足够大之后, h(n)给出了T(n)的一个确界。此时,我们记之为:
T(n) = Θ(h(n))
这里的Θ称作“大Θ记号” (big-Θ notation) ,它是对算法复杂度的准确估计

复杂度分析

常数O(1)

 问题与算法
首先考查如下问题:任给一个整数子集S, |S| = n ≥ 3,从中找出一个元素a ∈ S,使得
a ≠ max(S)且a ≠ min(S)。亦即,在最大、最小者之外任取一个元素,称作“非极端元素” 或“平常元素” 。
任取三个元素x, y, z ∈ S; //既然S是集合,返三个元素必于异
通过比较对它们做排序; //设排序结枅为:min{x, y, z}, median(x, y, z), max{x, y, z}
输出median(x, y, z);

对数O(logn)

 问题与算法

1
2
3
4
5
6
int i =1,n=1000,j=0;
while(i<n){

i*=2;
j++;
}

每次i乘以2,也就是说,至多经过1 + log2(n)次循环, i必然超过n,从而算法终止
由大O记号定义,在用函数logrn界定渐进复杂度时,常底数r的具体取值无所谓,故通常不予专门标出而笼统地记作logn
比如,尽管此处底数为常数2,却可直接记作O(logn)。
此类算法称作具有“对数时间复杂度”

线性O(n)

 问题与算法
考查如下问题:计算给定n个整数的总和。 该问题可由代码1.3中的算法sumI()解决。

1
2
3
4
5
6
int sumI(int A[], int n) { //数组求和算法(迭代版)
int sum = 0; //初始化累计器,O(1)
for (int i = 0; i < n; i++) //对全部共O(n)个元素,逐一
sum += A[i]; //累计,O(1)
return sum; //返回回累计值,O(1)
} //O(1) + O(n)*O(1) + O(1) = O(n+2) = O(n)

首先,对s的初始化需要O(1)时间。算法的主体部分是一个循环,每一轮循环中只需进行一次累加运算,这属于基本操作,可在O(1)时间内完成。
每经过一轮循环,都将一个元素累加至s,故总共需要做n轮循环, 于是该算法的运行时间应为:
O(1) + O(1)×n = O(n+1) = O(n)

多项式O(polynomial(n))

若运行时间可以表示和度量为T(n) = O(f(n))的形式,而且f(x)为多项式,则对应的算法称作“多项式时间复杂度算法” (polynomial-time algorithm)。
所实现起泡排序bubblesort()算法的时间复杂度应为T(n) = O(n^2), 故该算法即属于此类。
当然, 以上所介绍的线性时间复杂度算法, 也属于多项式时间复杂度算法的特例,其中线性多项式f(n) = n的次数为1

复杂度层次


常用的时间复杂度所耗费的时间从小到大依次是:
O(1) < O(logn) < (n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

02递归

线性递归

数组求和
以下仍以下数组求和问题为例,采用线性递归模式设计另一算法。首先注意到,若n =0则总和必为0,这也是最终的平凡情况。否则一般地,数组的总和可理解为前n-1个整数(即A[0,n-2])之和,再加上A[]的最后一个元素(即A[n-1])。 按这一思路,可设计出sum()算法如代码1.5所示

1
2
3
4
5
6
7
8
9
10
11
12
13
//线性递归,数组求和
public class Test {
public static void main(String[] args) {
int [] arr = {1,2,3};
int result = func(arr,arr.length);
System.out.println(result);
}
private static int func(int [] arr,int n){
return (n<1) ? 0:func(arr,n-1)+arr[n-1];
// n < 1平凡情况,递归基
//return 0; //直接(非递归式)计算
}
}

由此实例可看出递归算法保证有穷性的基本技巧。 具体地,首先必须判断并处理n = 0之类的平凡情况,以免因无限递归而导致系统溢出。这类平凡情况统称“递归基”(base case ofrecursion) 可能有多种平凡情况,但至少要有一种,且这类情况迟早必出现。比如,算法sum()的递归基只包含一种情况,只需简单地判断n是否已经减小到0

算法sum()是通过更深一层的自我调用来实现的,而且该函数的每一实例对自身的调用至多一次。于是,在每一层次上至多只有一个实例,且它们构成一个线性的次序关系。此类递归模式因而称作“线性递归” (linear recursion) ,它也是递归的最基本形式

该图清晰地给出了算法执行的整个过程:首先对参数n进行调用,再转向对参数n-1的调用,再转向对参数n-2的调用, …,直至最终的参数0。
在抵达递归基后不再递归,而是将平凡的解(长度为0数组的总和0)返回给对参数1的调用;累加上A[0]之后,再返回给对参数2的调用;
累加上A[1]之后,继续返回给对参数3的调用; …;如此依次返回,直到最终返回给对参数n的调用,此时,只需累加A[n-1]即得到整个数组的总和

时间复杂度:
具体地, 就以上的sum()算法而言,每一递归实例中非递归部分所涉及的计算无非三类(判断n是否为0、累加sum(n-1)与A[n-1]、返回当前总和) ,而且它们至多各执行一次。
鉴于它们均属于常数时间成本的基本操作,每个递归实例实际所需的计算时间都应为常数O(3)。由图还可以看出, 对于长度为n的输入数组,递归深度应为n+1,故整个sum()算法共需运行(n+1) * O(3) = O(n)时间

空间复杂度:
在创建了最后一个递归实例(即到达递归基)时,占用的空间量达到最大——准确地说,等于所有递归实例各自所占空间量的总和
这里每一递归实例所需存放的数据,无非是调用参数(数组A的起始地址和长度n)以及用于累加总和的临时变量
这些数据各自只需常数规模的空间,其总量也应为常数。
故此可知,sum()算法的空间复杂度线性正比于其递归的深度, 亦即O(n)

递归算法的空间复杂度:递归深度N*每次递归所要的辅助空间, 如果每次递归所需的辅助空间是常数,则递归的空间复杂度是 O(N).

减而治之

线性递归模式往往对应于所谓减而治之(decrease-and-conquer) 的算法策略:递归每深入一层,待求解问题的规模都缩减一个常数,直至最终蜕化为平凡的小(简单)问题。
按照减而治之策略,此处随着递归的深入,调用参数将单调地线性递减。因此无论最初输入的n有多大,递归调用的总次数都是有限的, 故算法的执行迟早会终止,即满足有穷性。当抵达递归基时,算法将执行非递归的计算(这里是返回0)

递推方程

该方法无需绘出具体的调用过程,而是通过对递归模式的数学归纳,导出关
于复杂度定界函数的递推方程(组)及其边界条件,从而将复杂度分析的任务转化为递归方程(组)的求解

仍以代码线性递归版sum()算法为例, 将该算法处理长度为n的数组所需的时间成本记作T(n)。
我们将该算法的思路重新表述如下:为解决问题sum(A, n),需递归地解决问题sum(A,n-1),然后累加上A[n-1]。
按照这一新的理解,求解sum(A, n)所需的时间,应该等于求解sum(A,n-1)所需的时间,另加一次整数加法运算所需的时间。

根据以上分析,可以得到关于T(n)的如下一般性的递推关系:
T(n) = T(n-1) + O(1) = T(n-1) + c1,其中c1为常数
另一方面,当递归过程抵达递归基时,求解平凡问题sum(A, 0)只需(用于直接返回0的)常数时间。
如此,即可获得如下边界条件:
T(0) = O(1) = c2, 其中c2为常数
联立以上两个方程, 最终可以解得:
T(n) = c1n + c2 = O(n)

递归算法的空间复杂度:递归深度N*每次递归所要的辅助空间, 如果每次递归所需的辅助空间是常数,则递归的空间复杂度是 O(N).

线性递归版sum()算法共需O(n)的附加空间

多递归基

为保证有穷性, 所有递归算法都首先必须设有递归基,且确保对应的语句总能执行到。
实际上, 针对算法中可能出现的每一类平凡情况,都需要设置对应的递归基,因此同一算法的递归基可能(显式或隐式地)不止一个。
以下考察数组倒置问题, 也就是将数组中各元素的次序前后翻转。 比如,若输入数组为:
A[] = {3, 1, 4, 1, 5, 9, 2, 6}
则倒置后为:
A[] = {6, 2, 9, 5, 1, 4, 1, 3}

1
2
3
4
5
6
7
8
9
10
11
12
13
//多递归基,数组倒置
private static void reserse(int [] a,int left,int right){
if(left<0 || right>=a.length){
return;
}
if(left < right){
int temp =a[left];
a[left] =a[right];
a[right] = temp;
reserse(a,left+1,right-1);
}
////else隐含了两种递归基
}

可见,每深入递归一层,待倒置区间的长度 left - right + 1都缩短2个单元。因此, 所有递归实例所对应区间长度的奇偶性一致。
需要特别留意的是, 此处递归基实际上分为两种情况: left = right(原数组长度为奇数)或left = right + 1(原数组长度为偶数)。当然,无论如何reverse()算法都必然会终止于这两种平凡情况之一,因此递归的深度应为:
[(n + 1) / 2] = O(n)

在算法终止之前,递归每深入一层都会通过一次对换使得当前的A[left]与A[right]就位,因此该算法的时间复杂度也应线性正比于递归深度,即O(n)。

二分递归

分而治之

面对输入规模庞大的应用问题,每每感慨于头绪纷杂而无从下手的你,不妨从先哲孙子的名言中获取灵感“凡治众如治寡,分数是也” 。是的,解决此类问题的有效方法之一,就是将其分解为若干规模更小的子问题, 再通过递归机制分别求解。 这种分解持续进行,直到子问题规模缩减至平凡情况。这也就是所谓的分而治之(divide-and-conquer) 策略

1
2
3
4
5
6
7
8
9
10
11
12
//二分递归,数组求和
private static int sum(int [] a,int left,int right){
if(left<0 || right>=a.length){
return -1;
}
if(left == right){
return a[left];
}
int medium = (left+right)/2;
return sum(a,left,medium) + sum(a,medium+1,right);

}


针对n = 8的情况给出了sum(A, 0, 7)执行过程的递归跟踪。其中各方框都标注有对应的lo和hi值, 即子数组区间的起、止单元。
可见,按照调用的关系及次序,该方法的所有实例构成一个层次结构(即二叉树)
沿着这个层次结构每下降一层,每个递归实例sum(lo, hi)都分裂为一对更小的实例sum(lo, mi)和sum(mi+1, hi)——准确地说,每经过一次递归调用, 子问题对应的数组区间长度hi-lo+1都将减半


算法启动后经连续m = log2n次递归调用,数组区间的长度从最初的n首次缩减至1,并到达第一个递归基。
实际上,刚到达任一递归基时,已执行的递归调用总是比递归返回多m = log2n次。
更一般地,到达区间长度为2^k的任一递归实例之前,已执行的递归调用总是比递归返回多m-k次。

因此,递归深度(即任一时刻的活跃递归实例的总数)不会超过m+1
鉴于每个递归实例仅需常数空间, 故除数组本身所占的空间,该算法只需要O(m+1) = O(logn)的附加空间。
我们还记得, 代码1.5 中线性递归版sum()算法共需O(n)的附加空间,就这一点而言,新的二分递归版sum()算法有很大改进

-------------本文结束感谢您的阅读-------------
感谢您的支持,我会继续努力的!
0%