利用差别算法，办理同一题目，服从大概相差很大
好比求n个斐波拉契数（前n项的和）、
斐波拉契数：一个数列从第3项开始，每一项都便是前两项之和
fib数列：0、1、1、2、3、5、8、13、21、34……
递归和平凡循环求解
public class fib{ public static int get1(int n){ if(n<=1){ return n; } int sum=get1(n-1)+get1(n-2); return sum; } public static int get2(int n){ if(n<=1){ return n; } first=0; second=1; int i=0; while(i<n-1){ sum=first+second; first=second; second=sum; i++; } return second; }}递归通常是把一个大型复杂的题目转化为一个与原题目相似的规模较小的题目，须要多次重复的盘算
图解：
前2项的和，0+1=1，须要举行一次加法运算
前3项的和，0+1=1，1+1=2，须要举行两次加法运算
……
前n项的和，须要举行n-1次加法运算
所用循环次数为n-1
递归方法时间复杂度：1+2+4+8=20+21+22+23=24-1=2n-1-1=0.5 x 2n-1= --->O(2n)
平凡循环方法时间复杂度：O(n)
循环方法时间复杂度分析：
for循环实行步调：
循环开始前设定好初始值且初始值 算作实行一次
别的部分按照下图 循环实行 直至条件不满足跳出循环
/*int i=0 实行一次i<4 实行4次i++ 实行4次输出语句实行4次时间复杂度 1+4+4+4*/for(int i=0;i<4,i++){ System.out.println("test");}/*外层循环 1+n+n内层循环 1+15+15+15时间复杂度 1+2n+n(1+15+15+15)*/for(int i=0;i<n;i++){ for(int j=0;j<15;j++){ System.out.println("test"); }}/*时间复杂度log5(n)分析：log5(n)即 5^x=nn=25,x=2n=125,x=3n=n/5n=25,循环2次n=125,循环3次*/while((n=n/5)>0){ System.out.println("test");}/*外层循环 1+2*log2(n)内层循环 1+3n 时间复杂度 1+2*log2(n)+log2(n)*(1+3n)*/for(int i=1;i<n;i=i*2){ for(int j=0;j<n;j++){ }}/*一样平常接纳大O体现法举行时间复杂度的估算
- 大O体现法是一种大略的分析模子，体现的是数据规模n对应的复杂度
一样平通例则：
1.忽略常熟、系数、低阶
2.对数一样平常省略底数
9-->O(1)2n+3-->O(n)n^2+2n+6-->O(n^2)4n^5+12-->O(n^5)
均派复杂度
举行添加操纵的时间，ArrayList提供了两种添加方法：
add(int index,E element);//中心插入
add(E element); //末端添加
末端添加通常环境下时间复杂度为O(1)，但是思量到最坏的环境大概会发生扩容，扩容则会举行拷贝数组的操纵，时间复杂度就变为了O(n)。但不会每次都是最坏环境，因此我们利用最坏的环境分析添加操纵的时间复杂度是不公道的。
17次根本操纵包罗了9次添加操纵 + 8次元素转移操纵。匀称每次addLast操纵，举行2次根本操纵（ 17/9 约便是2 ）
public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacity(size + 1); for (int i = size; i > index; i--) { elements = elements[i - 1]; } elements[index] = element; size++;}假设capacity=n，n+1次addLast，触发resize，统共举行2n+1次根本操纵
匀称，每次addLast操纵，举行2次根本操纵（ 2n+1/n+1 约便是 2 ）
将1次resize的时间平摊给了n+1次addLast的时间，于是得到了匀称每次addLast操纵举行2次根本操纵的结论
如许均派盘算，时间复杂度是O(1)级别的，这和我们数组中有多少个元素是没有关系的
在这个例子里，如许均派盘算，比盘算最坏环境是故意义的，这是由于最坏的环境是不会每次都出现的。
关于均派复杂度，着实在许多算法书中都不会举行先容，但是在现实工程中，如许的一个头脑是蛮故意义的：就是一个相对比力耗时的操纵，假如我们能包管他不会每次都被触发的话，那么这个相对比力耗时的操纵它相应的时间是可以分摊到别的的操纵中来的。
均派时间复杂度原文链接：https://blog.csdn.net/lemonZhaoTao/article/details/80379525
匀称环境时间复杂度
匀称环境时间复杂度与均派复杂度一样，也是在思量极度环境大概出现的概率不具有代表性，为了从差别角度阐明而引出地概念。
public boolean contains(E element) { // 最好：O(1) // 最坏：O(n) // 匀称：O(n) return indexOf(element) != ELEMENT_NOT_FOUND;}public int indexOf(E element) { if (element == null) { // 1 for (int i = 0; i < size; i++) { if (elements == null) return i; } } else { for (int i = 0; i < size; i++) { if (element.equals(elements)) return i; // n } } return ELEMENT_NOT_FOUND; }假如有链表的contains(E element)方法，要查找的元素element分为n+1种环境，在链表上面（0~n）和不在链表上面(0~n)。把每种环境下，查找须要遍历元素的个数累加起来，然后再除以n+1，就可以得到须要遍历元素个数的匀称值，即：
省略系数、低阶、常量后得O(n)
复杂度振荡须要先相识缩容机制
- 缩容
当数组剩余的存储空间较多时为了节流掉部分内存，可以思量举行缩容。
public E remove(int index){ rangeCheck(index); E old=elements[index]; for (int i=index+1;i<size;i++ ) { elements[i-1]=elements; } elements[size--]=null; trim(); return old;}private void trim() { int oldCapacity = elements.length; int newCapacity = oldCapacity*1/3; //小于默认数组容量或现实拥有元素数量大于缩容后容量则返回 if(size >= newCapacity || oldCapacity <= DEFAULT_CAPACITY) return; E[] newElements = (E[]) new Object[newCapacity]; for(int i = 0;i < size;i++) { newElements = elements; } elements = newElements;}
- 复杂度震荡
将上面的newCapacity稍作改动，可以或许方便我们更好地观察复杂度振荡
int newCapacity = oldCapacity>>1/2;以是复杂度振荡 是指在装满元素的环境下举行添加操纵将会立即触发扩容，之后若举行删除操纵将会立即触发缩容，扩容和缩容的时间复杂度都是O(n)
出现振荡的缘故起因是由于扩容和缩容之间的关系为：扩容2倍 x 缩容1/2倍=1
调解缩容倍数为1/3大概1/4... 复杂度振荡将消失 |
