0. 序言
如果你对简单的复杂度分析不了解，请跳转阅读：https://www.jianshu.com/p/2d5e5f1bc77e
如果你想看常见的时间复杂度实例分析，请跳转阅读：https://www.jianshu.com/p/4c8fa84a9393
阅读本篇文章，建议先跳转阅读：https://www.jianshu.com/p/08d1d509c5db
如果你对简单的复杂度分析以及常见的时间复杂度以及最好、最坏、平均时间复杂度已经了解，想对均摊时间复杂度有更多的了解，那么你可以阅读本篇文章，一定会让你有所收获。
1. 简介
均摊时间复杂度，在我看来，是平均时间复杂度的补充。平均时间复杂度只在某些特殊情况下才会用到，而均摊时间复杂度应用的场景比它更加特殊、更加有限。
2. 应用场景
// array 表示一个长度为 n 的数组
// 代码中的 array.length 就等于 n
int[] array = new int[n];
int count = 0;
void insert(int val) {
if (count == array.length) {
int sum = 0;
for (int i = 0; i < array.length; ++i) {
sum = sum + array[i];
}
array[0] = sum;
count = 1;
}
array[count] = val;
++count;
}
这段代码实现了往数据中插入数据的功能。当数组没有满的时候，直接插入数据到数组中。当数组满了以后，遍历数组求和，将求和之后的sum值放在数组中的第一位置，然后把count指针指向索引为1的位置，再将新的数据插入。
我们看下这段代码的最好、最坏、平均时间复杂度。当数组没有满的时候，直接将数据插入数组中即可，这是最理想的情况，所以最好时间复杂度为O(1)。当数组满的时候，需要遍历数组求和，把求和后的数据插入，这是最坏的情况，所以最坏情况的时间复杂度为O(n)。
平均时间复杂度是多少呢？我们分析下：假设数组的长度是n，根据数据插入的位置的不同，我们可以分为n种情况，每种情况的时间复杂度是O(1).当数组满了的时候插入一个数据，这个时候需要遍历求和，这个时候的时间复杂度是O(n)，而n+1种情况发生的概率一样，都是1/n+1。所以根据加权平均计算法，求得的平均时间复杂度是：
平均时间复杂度
以上的O(1)是去掉系数和常数得出来的结果。
但是你会发现这段代码平均时间复杂度的分析并不需要引入概率。我们对比下find示例（https://www.jianshu.com/p/08d1d509c5db）和以上insert示例，发现两者有很大区别：
① find函数在极端情况下，复杂度才为O(1),但insert在大部分情况下，时间复杂度都为O(1),只有个别情况下，时间复杂度才是O(n).
② insert函数，O(1)时间复杂度的插入和O(n)时间复杂度的插入，出现的频率都是有规律可循的，先是n个O(1)的插入，然后是O(n)的遍历求和插入，接着是1个O(1)的操作，紧跟着是n-1个O(1)的操作，然后循环往复后面三种操作。
综上你会发现，find操作在执行的时候，你并不知道find操作会执行多少次，因为数据不同，发生的find的概率不同，所以用加权平均时间复杂度分析比较合理，而insert操作在执行的时候，因为有规律可循，所以很多情况下，insert执行插入的位置的概率是100%的O(1)，而只有很少情况是O(n)——针对大部分执行100%概率是低阶，很少概率是高阶时间复杂度的情况，我们不适合用平均时间复杂度去分析，这个时候用均摊时间复杂度分析较为合理。
顾名思义：均摊复杂度，就是把量级高的操作所耗费的时间分担到量级低的操作上，看平摊后的量级是多少。拿上面的例子来说：每次O(n)的遍历求和操作后面，会跟着1次O(1)的插入操作，然后跟着n-1次O(1)的插入操作，所以把耗时多的遍历求和操作的时间均摊到接下来的n次耗时少的操作上，也就是平均执行2次操作，所以这一组连续的操作的均摊复杂度就是O(1)。
综上：对一个数据结构进行一组连续操作，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，适合运用均摊复杂度分析代码，而此时均摊时间复杂度就等于最好情况时间复杂度。
3. 后续
如果大家喜欢这篇文章，欢迎点赞！
如果想看更多 数据结构 方面的文章，欢迎关注!
网友评论