玩转数据结构java - 数组类5 - 均摊复杂度和防止复杂度的震荡

resize的复杂度分析：

 resize并不是每次操作都会被触发，只有邻近容量上限时才会resize，所以按照最坏的情况O(n)来作为它的复杂度并不合理。

那我们要怎样分析addLast(e)，包含resize的复杂度呢？

假设容量capacity是8，每个都是addLast，当第九次addLast操作时会触发resize，使复制8次到一个新数组，然后再增加第九个元素。也就是说，9次操作触发了一次resize操作，一共17次操作，对于9次addLast作，每次花费大概是17/9 约等于2，
也就是 capacity是n，当满了时，将会操作n次复制，然后＋1次增加操作，所以是2n + 1 次。2n+1 / n 。平均每次addLast进行了两次操作。

结论：
因为resize不是每次都会被触发，每n+1次触发一个resize，且为 2n+1次，将其平摊给n+1, 2n+1 / n+1。平均每次addLast进行两次操作，这样均摊复杂度计算后，addLast的时间复杂度是O(1)
在上面这个例子里，均摊计算比最坏时间复杂度有意义，因为最坏情况不会每次都出现。
同理addRemove的均摊复杂度也是O(1)

均摊复杂度：
一个相对比较耗时的操作，如果可以保证不会每次都触发，这个时间可以分摊到其他时间里。

复杂度震荡
当同时思考addLast removeLast 两个操作时

如果一个数组的capacity已满，然后addLast会马上扩容，然后再removeLast会马上缩减容量，再addLast，再removeLast。。。这样导致了反复的resize。每次操作都是O(n)，并不是上一个例子中的n+1次才会出现
明明均摊时想的挺好，但是就是有特殊的情况导致了复杂度猛地变量，导致了震荡。

出现问题的原因：
removeLast时，resize过于着急(Eager)，
解决方案：
Lazy 使用懒惰策略
当size == capacity/4 时，容积才减半
Lazy懒惰策略也适用于线段树

修改remove方法中resize

//要注意 data.length 有可能变成1 1/2=0  这时会发生错误，所以要注意
 if(size == data.length / 4 && data.length / 2 != 0) {
       //复用resize  可以变小也可以变大
       resize(data.length / 2);
  }

学习数据结构的方式：
怎样具体存储数据？
怎样在具体存储的基础上进行增删改查