先举个栗子
分析以下这段代码的时间复杂度
// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) pos = i;
}
return pos;
}
分析
- 功能：在一个无序数组array中，查找变量x出现的位置
- 时间复杂度：
O(n), n表示数组的长度
更为优化的方式
// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) {
pos = i;
break;
}
}
return pos;
}
时间复杂度： 不一定是O(n)了，不同情况下这段代码的时间复杂度是不同的。
引入概念
-
最好情况时间复杂度：在最理想情况下，执行代码的时间复杂度
-
最坏情况时间复杂度：在最糟糕情况下，执行代码的时间复杂度
-
平均情况时间复杂度：最好情况和最坏情况都是属于极端情况，发生的概率并不大。需要表示平均情况下的复杂度
如何分析平均情况时间复杂度
以上面的例子为例：查找x在数组中的位置，有n+1种情况，在数组0~n-1的位置上和不在数组中。
将每种情况下，查找需要遍历的元素个数相加，再除以n+1种情况，就可得到需要遍历的元素个数的平均值
(1+2+3+...+n+n)/n+1 = n (n+3) /2(n+1)
省略掉系数、低阶、常量后得到平均时间复杂度为O(n)
存在问题
在以上的n+1种情况中，未考虑x在每种情况下出现的概率。
现在假设，x在数组中与x不在数组中的概率各为1/2；
要查找的x出现在0~n-1这n个位置的可能性是相同的，即1/n；
那么，要查找的x出现在0~n-1中任意位置的概率为 1/2*1/n = 1/(2n)
将每种情况发生的概率考虑进去后，平均时间复杂度计算过程变成：
这个值就是概率论中的加权平均值，也叫作期望值。因而平均时间复杂度的全称为加权平均时间复杂度或期望时间复杂度。
注：很多时候，我们只使用一个复杂度就可以满足要求。只有同一块代码在不同情况下，时间复杂度有量级的差距，才会使用以上3种复杂度的表示法来区分。
均摊时间复杂度、摊还分析（平摊分析）
举栗子说明：
// 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;
}
分析
-
功能：实现了往数组中插入数据的功能。
-
具体：
1 . 当数组满了count == array.length,就用for循环遍历求和，将求得的和放在数组的第一个位置，并清空数组其余元素；然后再插入新的元素。
2 . 当数组一开始就有空闲，则直接将数据插入数组。 -
复杂度分析：
1 . 最好情况：数组中有空闲，直接将数据插入到count的位置，为O(1)
2 . 最坏情况：数组没有空闲空间，需要先做一个遍历求和，再作插入。所以复杂度为O(n)
3 . 平均时间复杂度：O(1)
平均时间复杂度如何得到
总共n+1种情况，前n中情况每种时间复杂度都为O(1)，后一种情况时间复杂度为O(n)；n+1种情况发生的概率一样，为1/(n+1)；根据加权平均计算方法：
1*1/(n+1) + 1*1/(n+1) + ... + n*1/(n+1) = O(1)
均摊时间复杂度（amortized time complexity）
分析发现:
1 . insert()函数在大部分情况下，时间复杂度都为O(1)；极个别情况下，复杂度才高，为O(n)
2 . insert()函数中，O(1)时间复杂度的插入和O(n)时间复杂度的插入，出现频率很有规律。存在前后时序关系，一般一个O(n)插入之后，紧跟着n-1个O(1)的插入操作，循环往复。
针对这种场景，引入均摊分析法
大致思路：每一次 O(n) 的插入操作，都会跟着 n-1 次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)。
总结
对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。
而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。
均摊时间复杂度就是一种特殊的平均时间复杂度，没必要花太多精力去区分它们。