04 | 复杂度分析（下）：浅析最好、最坏、平均、均摊时间复杂度
Page content
[TOC]
浅析最好、最坏、平均、均摊时间复杂度
04 | 复杂度分析（下）：浅析最好、最坏、平均、均摊时间复杂度
复杂度的分类
1、最好情况时间复杂度（best case time complexity）
2、最坏情况时间复杂度（worst case time complexity）
3、平均情况时间复杂度（average case time complexity）
考虑概率时，加权平均时间复杂度，也叫作期望时间复杂度。考虑了概率。
4、均摊时间复杂度（amortized time complexity）
又叫做摊还分析，平摊分析
// 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;
}
例如一个函数中，不同复杂度的操作按照一定的频率出现。例如O(1) O(N)的复杂度交替出现。尽管很多数据结构和算法书籍都花了很大力气来区分平均时间复杂度和均摊时间复杂度，但其实我个人认为，均摊时间复杂度就是一种特殊的平均时间复杂度，我们没必要花太多精力去区分它们。你最应该掌握的是它的分析方法，摊还分析。至于分析出来的结果是叫平均还是叫均摊，这只是个说法，并不重要。
我们还是继续看在数组中插入数据的这个例子。每一次 O(n) 的插入操作，都会跟着 n-1 次 O(1) 的插入操作，所以把耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O(1)。这就是均摊分析的大致思路。你都理解了吗？
内容小结
为什么要引入这么多复杂度的概念？因为，同一段代码，在不同的输入情况下，复杂度量级有可能是不一样的。
引入这样的概念之后，能让我们可以更加全面的表示一段代码的执行效率。
思考
分析这个函数的复杂度
// 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;
}
