均摊时间复杂度

均摊时间复杂度与平均时间复杂度有点类似，因此非常容易混淆。平均时间复杂度只在某些特殊情况下才会用到，而均摊时间复杂度应用的场景比它更加特殊、更加有限。

下面借助一个例子来理解均摊时间复杂度：

const array: number[] = new Array(10);
let count = 0;
function insert(val: number) {
    // 当 count 等于数组长度的时候，对数组中的所有元素求和，并将和放置到数组第一位中
    if (count === array.length) {
        let sum = 0;
        for (let i = 0; i < array.length; i++) {
            sum = sum + array[i];
        }
        array[0] = sum;
        count = 1;
    }
    array[count] = val;
    count++; 
}

在分析这段代码的时间复杂度之前，首先先分析一下这个代码的功能，这段代码的功能并不复杂，通过 insert 函数往 array 数组插入数字，当 array 数组元素已经填充满的时候，会将数组中的所有元素进行求和，并将所求的和放在元素的第一个位置中进行保存。

这段代码我们可以使用最好情况时间复杂度、最坏情况时间复杂度、平均情况事件复杂度来进行分析。这里一共有 种情况，分别为数组未填满的时候往数组插入数字的 n 种情况，以及数组填满之后往数组插入数字的一种情况。

最理想的情况就是插入数字的时候，数组中仍然有位置，这个时候的时间复杂度为 。在最坏的情况下，数字插入到数组的时候，数组已经处于填满数字的情况，这时候的时间复杂度为。平均情况时间复杂度为 。

均摊时间复杂度

通过上面的计算过程，我们得到了代码的时间复杂度，但其实上面的例子计算时间复杂度的时候，并不需要弄得那么复杂。首先例子大部分的情况时间复杂度都为，只有极端情况下才是。另外复杂度为 的插入与复杂度为 的插入出现得非常有规律，针对这样一种特殊场景的复杂度分析，其实并不需要向前面那样子弄得那么复杂。为了应对这一场景，引入一种更为简单的摊还分析法，其得到的时间复杂度为均摊时间复杂度。

下面我们来使用摊还分析法来分析时间复杂度。上面的例子在进行完一次复杂度为 的操作之后，会进行 n-1 此复杂度为 的操作，这种前后连贯的时序关系，可以将它作为一组操作进行分析，将较高时间复杂度的操作均摊到其他时间复杂度比较低的操作上。将 复杂度的操作均摊到 n-1 此复杂度为 的操作上，可以得出这组操作的时间复杂度为 。

从上面的分析可以得知，均摊时间复杂度其实就是特殊的平均情况时间复杂度。