三、时间复杂度分析
3.1 基础
五种常见的时间复杂度
O(1)：常数复杂度, 最快的算法，数组的存取是O(1)
O(n)：线性复杂度, 例如：数组, 以遍历的方式在其中查找元素
O(logN)：对数复杂度
O(nlogn)：求两个数组的交集, 其中一个是有序数组，A数组每一个元素都要在B数组中进行查找操作，每次查找如果使用二分法则复杂度是 logN
O(n2)：平方复杂度，求两个无序数组的交集
在这里，大O描述的是算法的运行时间和输入数据之间的关系
3.2 举例说明
大家可以看下面一个例子
public static int sum(int[] nums){ int sum = 0; for(int num: nums) sum += num; return sum; }
这个算法是 O(n) 复杂度的，其中 n是nums中的元素个数，算法和n呈线性关系
为什么说他是 O(n) 的时间复杂度呢，因为这个算法运行的时间的多少是和 nums 中元素的个数成线性关系的，那么这个线性关系，表现在我们的 n 是一次方，它不是 O(n) 方的，也不是 O(n) 的立方，n 对应的是一次方。
我们忽略常数，实际时间是： T = c1*n+c2
c1：我们要把这个数据从 nums 数组中取出来，其次我们还要把 sum 这个数取出来，然后 num 这个数和 sum 相加，最终呢我们要这个结果扔回给 sum 中
c2：开始开辟了一个Int型的空间，我们把它叫 sum ，要把 0 初始化赋值给sum，在最终呢我们还要把这个 sum 给 return 回去
一方面把 c1 和 c2 具体分析出来是不大必要的，另一方面也是不太可能的，为什么说不可能呢？如果说把 num 从 nums 中取出来，基于 不同的语言，基于 不同的实现，它实际运行的 时间是不等的，就算转换成机器码，它对应的机器码的指令数也有可能是不同的，就算是指令数是相同的，同样的一个指令，在我们 cpu 的底层，你使用的 cpu 不同，很有可能，执行的操作也是不同的，所以在实际上我们可能说出 c1 是几条指令，但是却很难说出 c1 到底是多少，c2也是同理，正因为如此，我们在进行时间复杂度时，是忽略这些常数的。
忽略这些常数就意味着什么，就意味着这些 t = 2*n +2 和 t=2000*n+10000算法这些都是 O(n) 的算法，见下面列表：换句话说他们都是线性数据的算法，也就是说我们这个算法消耗的时间是和我们输入数据的规模成一个线性相关的，t=1*n*n+0也线性算法是和我们成平方关系的 ，他的性能比上面的差，因为他是 O(n^2)的
算法 时间复杂度
T = 2*n + 2 O(n)
T = 2000*n + 10000 O(n)
T = 1nn + 0 O(n^2)
T = 2nn + 300n + 10 O(n^2)
O(n)和O(n^2)并不代表说 O(n)的算法快于 O(n^2)的算法，我们要看 n 的常数，比如 n=3000 的时候，或者 n>3000 的时候，O(n^2)消耗的时间是远远大于 O(n)的，n越大 O(n)远远快于 O(n^2)
O：描述的是一个算法，也就是说渐进时间复杂度
当高阶向和低阶项同时出现的时候，低阶项会被忽略，比如说：T = 2*n*n + 300n + 10当中 2*n*n，是O(n^2)级别的算法，属于高阶项，300n是O(n)的算法低阶项，当n无穷大的时候，低阶项起的作用很小。
3.3 分析动态数组的时间复杂度
3.3.1 添加操作
添加操作 总体来说属于 O(n) 级别的复杂度，如下列表
添加方法 时间复杂度
addLast(e) O(1)
addFirst(e) O(n)
add(index,e) O(n/2) = O(n)
在程序设计中，我们要采用最严谨的设计，需要考虑到最坏的情况，所以我们说添加操作时属于 O(n) 级别的复杂度，是因为我们在 addLast 的时候，有可能会进行 resize 的操作，我们从最坏的情况分析是对的，但是 addLast 不可能每次都是进行 resize 操作，比如 size 有十个，我们要添加十个元素后才会触发一个 resize ,我们要在添加十个元素才会触发一个 resize，因此我们使用最坏情况进行分析的是不合理的，那么分析 addLast 时间复杂度呢，请看下面小节。
3.3.2 resize的复杂度分析
总共进行了17次基本操作：9次添加操作8次元素转移操作
9次addLast操作，触发resize，总共进行了17次基本操作，平均每次addLast操作，进行了2次基本操作
假设 capacity = n，n+1 次addLast，触发resize，总共进行了2n+1次基本操作，平均，每次addLast操作，进行了2次基本操作
这样均摊计算，时间复杂度是O(1)的，在这个例子里，这样均摊计算，比计算最坏情况有意义
addLast 均摊复杂度是O(1)的，同理我们看 removeLast操作，均摊复杂度也是O(1)
3.3.3 复杂度震荡
当我们数组容量满了的时候，因为是动态数组，回去自动扩容，我们又马上去remove 一个操作的时候，因为数组容量小于 初始容量的一半的时候，又会 自动 resize缩减为一半的大小，如此操作，就会一个问题，就是我们在 removeLast的时候 resize 过于着急(Eager)
解决方案：Lazy，懒散的，其实也很简单，如下图所示：
当我们的 size == capacity /4 时候，才将capacity 减半，实现方式如下：
//从数组中删除index位置的元素，返回删除的元素 public E remove(int index){ if(index < 0 || index >= size) throw new IllegalArgumentException("remove failed . Index is illegal."); E ret = data[index]; for (int i = index+1 ; i < size; i++) data[i - 1] = data[i]; size--; // loitering objects != memory leak data[size] = null;//如果一旦使用新的元素，添加新的对象就会覆盖掉 if(size == data.length / 4 && data.length / 2 != 0) resize(data.length / 2); return ret; }
完整代码：
package com.bj.array; /** * @program: Data-Structures * @ClassName Array * @description: * @author: lyy * @create: 2019-11-18 22:27 * @Version 1.0 **/ public class ArrayPlus<E> { private E[] data; private int size; //构造函数，传入数组的容量capacity 构造array public ArrayPlus(int capacity){ data = (E[])new Object[capacity]; size = 0; } //无参数的构造函数，传入数组的容量capacity=10 public ArrayPlus(){ this(10); } //获取元素中的个数 public int getSize(){ return size; } //获取数组的容量 public int getCapacity(){ return data.length; } //返回数组是否为空 public boolean isEmpty(){ return size == 0; } //在所有元素后添加一个新元素 public void addLast(E e){ add(size,e); } //想所有元素前添加一个新元素 public void addFirst(E e){ add(0,e); } //在第Index个位置插入一个新元素e public void add(int index,E e){ if(index < 0 || index > size) throw new IllegalArgumentException("Add failed . Require index < 0 || index > size."); if(size == data.length) resize(2 * data.length); for (int i = size - 1; i >= index ; i--) data[i+1] = data[i]; data[index] = e; size++; } //获取index索引位置的元素 public E get(int index){ if(index < 0 || index >= size) throw new IllegalArgumentException("Get failed . Index is illegal."); return data[index]; } //修改index索引位置的元素为e public void set(int index,E e){ if(index < 0 || index >= size) throw new IllegalArgumentException("Set failed . Index is illegal."); data[index] = e; } //查找数组中是否有元素e public boolean contains(E e){ for (int i = 0; i < size; i++) { if(data[i].equals(e)) return true; } return false; } //查找数组中元素e所在的索引，如果不存在元素e，则返回-1 public int find(E e){ for (int i = 0; i < size; i++) { if(data[i].equals(e)) return i; } return -1; } //从数组中删除index位置的元素，返回删除的元素 public E remove(int index){ if(index < 0 || index >= size) throw new IllegalArgumentException("remove failed . Index is illegal."); E ret = data[index]; for (int i = index+1 ; i < size; i++) data[i - 1] = data[i]; size--; // loitering objects != memory leak data[size] = null;//如果一旦使用新的元素，添加新的对象就会覆盖掉 if(size == data.length / 4 && data.length / 2 != 0) resize(data.length / 2); return ret; } //从数组中删除第一个位置的元素，返回删除的元素 public E removeFirst(){ return remove(0); } //从数组中删除最后一个位置的元素，返回删除的元素 public E removeLast(){ return remove(size-1); } //从数组中删除元素e //思考？如果返回是否删除成功 2、如果存在重复数据，如何删除多个 public void removeElement(E e){ int index = find(e); if(index != -1) remove(index); } @Override public String toString(){ StringBuffer res = new StringBuffer(); res.append(String.format("Array：Size = %d，capacity = %d\n",size,data.length)); res.append("["); for (int i = 0; i < size; i++) { res.append(data[i]); if(i != size - 1) res.append("，"); } res.append("]"); return res.toString(); } private void resize(int newCapacity) { E[] newData = (E[])new Object[newCapacity]; for (int i = 0; i < size; i++) newData[i] = data[i]; data = newData; } }
