0x07-学习玩转数据结构-均摊复杂度、复杂度震荡

1、复杂度分析

我们现在所实现的这个动态数组，对于添加操作来说，它的时间复杂度是O(n)的。是因为对于我的时间复杂度来说，通常我们都是考虑最坏的情况，虽然在尾部添加1个元素，它的时间复杂度是O(1)的。但是我们不能仅仅考虑这种情况，正是因为如此对于通常的这种动态数组，添加操作时间复杂度是O(n)级别的。但是如果我们保证添加元素的时候，只在我们组的尾部添加元素的话，换句话说，我肯定inserFirst和insert这两个方法，我根本不用的话，很显然，此时这个添加操作，它的时间复杂度就变成O(1)的了。但是由于对我们的动态数组来说，有resize这个方法。思考一下，我们的复杂度分析分析的都是最最坏的情况，在这种情况下最坏的情况就是insertLast了，添加1个元素，同时也要进行扩容，由于这个扩容是一个O(n)级别的复杂度，所以使得我们整个添加操作依然是O(n)级别的。

image

2、不是每次都最坏

当然，我从最坏的角度这么分析是对的，但是这里我们忽略了一个问题。这个问题其实就是我们不可能每一次添加元素的时候，都触碰这个resize操作。根据我们之前的逻辑，假设我们的数组有十个空间，那么我们要添加10次元素之后，才会触发一次resize，而触发这一次resize之后，我们的数组的容量就会变成20。此时我们添加元素要再添加10个元素才会再触发一次resize，之后我们整个数组空间就会变成40，我们要再添加20次元素，才会再触发一次resize，以此类推。我们根本不可能每次添加元素都触发这个resize，正因为如此对于这种情况我们使用最坏的情况分析是稍微有一些不合理的，此时我们应该怎么分析这个insertLast的时间复杂度呢？

image

3、均摊分析

我们可以这样的来看这个问题，假设当前我这个数组容量为8的话，并且我每一次添加都使用insertLast，也就是在添加元素这一部上我都是O(1)的复杂度。很显然我需要经过8次元素的添加，每一次都是O(1)的复杂度。之后我再添加第9个元素的时候，我就发现我现在的数组已经满了，所以首先我要resize一下。那么这个resize操作，我要把之前添加的八个元素全都复制到新的这个静态数组中。所以消耗8的时间，之后我再添加这一次元素再加上1。也就是整体上，我这九次操作就触发了一次resize，总共的其实进行了17次基本的操作。在这里，我们假想这个基本的操作就是给一个空间赋上一个值，那么这17次基本操作就是9次的添加操作和8次的这个元素转移的操作。这样来看的话，相当于对于这9次操作，平均来讲，每次这个insertLast操作大概进行了两次基本操作，那么这个计算方法是17÷9他比2了还少一些，但是呢，在这里我约等于2了。换句话说，我们把这个结论再推广一下，假设我们当前这个数组容量等于n的话，那么相当于我要进行n加1次的添加操作才会触发一次resize。总共进行了2n加1次基本操作。这个2n加1的计算方法就是n加上这个n加1，那么用2n加1除以n加1，平均来讲其实我们每一次的insertLast操作进行了两次基本操作。同学们可以仔细思考一下这样的一种计算方式，相当于是说我在考虑我的resize操作实际上不可能每次insertLast的时候都会触发一次resize。所以我综合n加1次insertLast，那么n加1次insertLast其实只会触发一次的resize，我将这一次resize的时间平摊给了这n加1次的insertLast。

image

4、均摊时间复杂度

于是得到了这个结论，平均每一次这个inserLast的操作进行了两次基本操作，平均每次进行两次基本操作，意味着什么？意味着这样来算的话，我们的这个insertLast操作它的时间复杂度是O(1)级别的，它和我们当前这个数组中有多少个元素是完全没有关系的。在我们的这个例子里其实这样均摊计算比计算最坏的情况是有意义的，这就是因为那个最坏的情况不会每次都出现。那么，我们这样计算复杂度就称之为是均摊复杂度，关于均摊复杂度，其实，很多算法的教材中可能都不进行介绍，但是在实际工程中，这样的一个思想的还是蛮有意义的。就是一个相对比较耗时的操作，如果我们能保证他不会每次都触发的话，那么这个相对比较耗时的操作，相应的这个时间是可以分摊到其它的操作中来的。我们用同样的思考，也可以想象removeLast的这个操作，虽然它的最坏时间复杂度O(n)级别的，但是它的均摊复杂度也是O(1)级别的。

image

5、极端情况考虑

现在我们通过均摊复杂度的分析，看起来insertLast和removeLast这两个操作，其实都是O(1)级别的操作。可是当我们同时思考这两个操作的时候出现了一个问题，这个问题呢，通常称为复杂度的震荡。这个问题是什么呢？我们简单的来看一下，假设现在我们有一个数组，他们这个数组，它的容量的是n，并且呢，现在已经装满了这个元素。那么想象一下此时我再调用一下insertLast这个操作的话，添加1个新的元素，显然要扩容。那么这个扩容的过程就会耗费O(n)的时间。之后，马上进行removeLast的这个操作，根据我们之前的逻辑，在上一个操作里，由于我扩容了扩容之后，我现在的容量的其实就变成2n了。现在我又把刚刚添加的那个元素给删除了，在删除之后，现在我这个数组中的元素数是n，n是2n的二分之一。所以此时对于removeLast这个操作我们触发了它的这个缩容的过程，也就是又要调用一遍resize，它的时间复杂度依然是O(n)的。在这种情况下，假如我又添加了一次元素，再调一次insertLast，其实重复了一下之前的过程，现在由于我的容积是n的，那么我就又要扩容扩容到2n的情况，时间复杂度是O(n)级别的。之后我再进行一下删除操作，删除之后，我现在这个数组中的元素有n个元素，他是当前2n这个容积的二分之一。所以我要再进行缩容，这个缩绒的过程又耗费O(n)的时间。我之前曾经说过，对于调用insertLast和removeLast的来说都是每隔n次，才会触发一次resize，而不会每次都触发resize。但是现在我们制造了一个情景，当我们同时看这个insertLast和removeLast的时候，存在某种情况，每一次都会耗费O(n)的复杂度，这就是复杂度的震荡。

image

6、复杂度震荡

明明在均摊的时候，我们想的挺好，应该变成一个O(1)的复杂度，但是在一些特殊的情况下，这个复杂度猛地蹿到了O(n)这个级别，产生了这个震荡。对于这个问题应该怎么解决呢？我们可以简单的来分析一下，这个问题发生的原因是什么？出问题的原因，其实在于removeLast的时候，我们resize的有些过于着急，也就是说我们采用了一种，有的时候称为是非常激进的非常急的一个策略。我们的元素变为当前容积的二分之一的时候，我们马上就把当前的容积也缩绒成为了二分之一，此时，我们整个数组中元素是满的，也就是元素的个数和容积的数量是相等的。那么，在这种情况下，我们再添加1个元素，自然而然的就需要进行扩容了。解决方案是什么？

7、懒惰的解决方案

解决方案是使用相对来说更加懒惰一些的策略。那么，这是什么意思呢？我们可以看一下，比如说当前这个数组初始的时候，它的容积是n，元素是空的，当我们把这个数组的元素全都填满的时候。根据我们刚才的设计，此时我们再添加1个元素，那么我们就需要扩容了，这是一定的。因为我们添加元素的时候，如果容量不够的话，只能通过扩容来处理，但关键在于当我们删除1个元素的时候，那么此时我们数组中的元素数量是容积的二分之一了，不着急，现在就把我们的整个动态数组的容量进行缩容。而是再等等，如果后面一直有删除操作的话，删除到了是整个数组容积的四分一了，那么此时，我们再来说，看来现在我们的这个数组确实是用不了这么大的空间。我们再进行缩容，但是缩容只缩容整个数组的二分之一的空间，我们还预留出了一半的空间。在这种情况下，如果我们再要添加元素，也不需要马上就触发扩容操作。我们的策略就变成了，我们数组中的元素数是我们整个容积的四分之一的时候，才将整个容积减半，也就是说我们犯懒了，不是在数组中的元素数是容积的一半的时候，我们就马上把这个容积变成一半了。通过这样的策略我们就防止了复杂度的震荡，这种懒惰的方式，其实是很有意思的一种方式，在算法的领域，有的时候我们懒一些，反而最终算法的整体性能会更好。在后续我讲到线段树的时候，还会有这样的一个例子，大家会看到。当我们更懒的时候，其实是在改善我们的算法性能，不过在这里，同学们不要误会，我们说，我们的算法更懒，不代表这个代码容易编写，也不代表代码量更少，那么在后续。那个线段树的例子中同学们就会看到，其实我们要向加入这个懒的机制，反而要写更多的代码，对于这点的同学，现在先有个印象就好了。

8、代码实现

那么下面呢？我们把我们的这种懒的策略，实际用编程的方式反应在自己的这个动态数据相应的代码中。

// 删除某个位置上的元素
int AMGArray::remove(int index) {
    if ( index < 0 || index >= size ) {
        cout << "remove Index 不合法 " << index << endl;
        return -1;
    }
    // 从index位置开始往后赋值
    for (int i = index; i < size - 1; i++) {
        data[i] = data[i + 1];
    }
    int res = data[index];
    data[size - 1] = 0;  // 游荡元素
    size--;
    // 缩容
    if ( size == capacity / 4 && 0 != capacity / 2 ) {
        resize(capacity / 2);
    }
    return res;
}