数据结构与算法基础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)

 问题与算法

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()解决。

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所示

//线性递归,数组求和
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}

//多递归基，数组倒置
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） 策略

//二分递归，数组求和
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()算法有很大改进