前言
我们平常分析复杂度一般是分析一个算法从头运行到尾它的复杂度是怎样的。但我们在项目中经常会写一个复杂度较高的算法，但是这个高复杂度的算法是为了方便其他操作。此时我们通常会将这个复杂度较高的算法和其他的操作放在一起来分析复杂度。这个复杂度较高的算法复杂度将会均摊到其他的操作中。这种复杂度分析法我们就叫做均摊复杂度分析法。最典型的例子就是我们写一个动态数组这样的一个类。动态数组每添加一个元素，或者删除一个元素。我们就要用到均摊复杂度分析法。
均摊复杂度案例分析
（1）我们先写出实现动态数组MyVector类的基本框架
import java.util.Arrays;
public class MyVector<Item> {
private Item[] data;
private int size; // 存储数组中的元素个数
private int capacity; // 存储数组中可以容纳的最大的元素个数
public MyVector(){
data = (Item[])new Object[100];
size = 0;
capacity = 100;
}
}
（2）为数组中添加一个元素
// 平均复杂度为 O(1)
public void push_back(Item e){
if(size == capacity) //元素个数等于数组容量
resize(2 * capacity); //为数组扩容将在下面讲到
data[size++] = e;
}
（3）从数组中拿出一个元素
// 平均复杂度为 O(1)
public Item pop_back(){
if(size <= 0)
throw new IllegalArgumentException("can not pop back for empty vector.");
Item ret = data[size-1];
size --;
// 在size达到静态数组最大容量的1/4时才进行resize，原因请往下看
// resize的容量是当前最大容量的1/2
// 防止复杂度的震荡
if(size == capacity / 4)
resize(capacity / 2);
return ret;
}
（4）当添加，删除元素，执行到一定时候，我们就要对数组进行扩容，缩容操作。即resize()方法。它的复杂度是O(n)级别的。
// 复杂度为 O(n)
private void resize(int newCapacity){
if(newCapacity < size)
throw new IllegalArgumentException("newCapacity can't be less than size.");
Item[] newData = (Item[])new Object[newCapacity];
for(int i = 0 ; i < size ; i ++)
newData[i] = data[i];
data = newData;
capacity = newCapacity;
}
（5）通过对上面的动态数组的操作为例。我们来进行均摊复杂度分析
1.png
假设我们的数组长度为n,那么我们每进行一次添加操作，他的算法复杂度为O(1)
2.png
当我们添加到最后一个元素时，如果此时再往里添加一个元素，那么就将进行数组的扩容操作。这次扩容的算法复杂度为O(n),此时我们就要用到均摊复杂度分析法，前面n次操作耗费时间总共为n,第n+1次操作耗费时间为n,相当于执行n+1次操作耗费的时间为2n,那么平均来看，我们每次操作其实耗费的时间为2，他仍然是一个O(1)级别的算法。在这里我把一次线性操作(第n+1次)的复杂度均摊到前面n次操作中。这就是典型的均摊复杂度分析。那么我们再看看这个数组删除操作他的复杂度是怎样的。
3.png
此时假设经过前面的添加操作数组容量变为2n,同样每次执行一次删除操作，时间复杂度为O(1)级别的。
4.png
同样当我们删除元素，删除到一定程度时，为了避免空间的浪费，就要对数组进行缩容。是不是可以引用前面数组扩容的思路，当数组元素的个数，等于当前数组容量的1/2时，就将数组容量减小一半。那么前面(n-1)次操作耗费时间总和为(n-1),第n次操作耗费时间为(n+1),n为对数组进行缩容操作耗时，1为删除这个元素耗时。所以均摊来看每次耗费时间仍然是2，时间复杂度为O(1)。那么如果你这样做的话你可能迎来一个新的问题——复杂度震荡
5.png
当我们删除元素，删除到数组元素个数为数组容量的1/2时。按照前面的思路。此时我们进行了缩容操作。变成下面了这副图。
6.png
如果刚好业务凑巧，前面刚进行了一次删除，对数组进行了一次缩容操作。后面又紧接着进行了一次数组的添加操作。因为我们知道当对数组进行缩容操作时，数组元素个数刚好等于数组的容量。此时如果再添加一个元素。那么我们就要进行扩容操作。不管是扩容还是缩容那么他的复杂度都是O(n)级别的。如果在这时一直重复进行删除，添加操作。那么整个算法的复杂度将由原来的O(1)级别上升到O(n)级别。这就是所谓的复杂度震荡。
7.png
出现复杂度震荡肯定是不好的，那我们如何来解决这个问题呢，其实很简单。就是我们推迟数组的缩容操作。当元素个数等于数组容量的1/4时，再进行缩容操作，缩容为当前数组容量的1/2。这样数组就有了剩余的空间，无论是添加还是删除。都是O(1)级别的。你学会了吗？
最后说两件事
1.中秋活动的中奖名单已出，如下，没写联系方式的尽快写上。好给你发红包。
8.jpg
2.最近创建了个免费的知识星球——读书会，欢迎大家加入。一起分享交流。
9.jpg
更多内容欢迎大家关注
yuandatou
网友评论