浅析最好、最坏、平均、均摊时间复杂度
最好、最坏时间复杂度#
举例一段代码：
// 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)$ 吗？恐怕不是了。
当在这种情况下，代码的时间复杂度是需要分情况讨论的，那么就会有以下几种时间复杂度：
最好情况时间复杂度：在理想情况下，执行这段代码的时间复杂度。在这个例子中，如果我们非常欧，在 array [0] 就找到了这个数，那么整段代码到这里就停止了。此时，这段代码的时间复杂度为 $O (1)$。
最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度。在这个例子中，如果我们非常非，在 array [n-1] 找到了，或者根本就没找到这个数，那么整段代码需要完整的遍历这个数组。此时，这段代码的时间复杂度为 $O (n)$。
平均时间复杂度#
那么，最好情况时间复杂度和最坏情况时间复杂度，可能都太极端了，其发生的概率可能并不大，是不能客观表示这段代码的时间复杂度的。那为了更好地表示平均情况下的复杂度，我们需要引入平均时间复杂度的概念。
回到上面那个例子中，变量 x 在数组中的位置，可能会有 n+1 种情况：在数组的 [0]~[n-1] 位置上(n) 或者不在数组中(1)。我们把每种情况下，找出这个数所需要遍历的元素个数累加起来，除以这 n+1 种情况，就可以得到为了找出这个数，需要遍历的元素个数的平均值，也就是：
那么，根据时间复杂度的大 O 标记法，系数、常量、低阶皆可忽略。所以简化之后，得到的平均时间复杂度就是 $O (n)$.
3月18日，存疑，到底是怎么简化的？搞不懂搞不懂。难道是这种分数形式就看最高阶是什么即可了吗？
3月19日，答疑，怎么简化的？根据leetcode里大佬的解释，举一反三，可得n(n+3) / 2(n+1)展开为(n^2+3n) / (2n+2)，由于常数可忽略，所以可简化为(n^2+3n) / (2n) = (n+3) / 2，所以化解之后的平均时间复杂度就是O(n)！！！
那么，对于这个结论，还有一些小问题。变量 x 在数组中的位置的 n+1 种情况，其发生概率并不是一样的。
那么首先，变量 x 在不在数组里？为了简化，我们假设在数组中与不在数组中的概率都为 $1 \over 2$。另外，在数组中出现在 [0]～[n-1] 这 n 个位置的概率也是一样的，为 $1 \over n$。所以，根据概率乘法法则，要找的数据出现在 [0]~[n-1] 中任意位置的概率就是 $1 \over 2n$
那么，这次我们将各种情况发生的概率考虑进去之后，平均复杂度的计算过程就变成了这样：
这个值就是概率论中的加权平均值，也叫做期望值，所以平均时间复杂度的全称应该叫加权平均时间复杂度或者期望时间复杂度
最后，这段代码的加权平均时间复杂度仍然是 $O (n)$。
实际上，在大多数情况下，我们并不需要区分最好、最坏、平均情况时间复杂度三种情况。只有同一块代码在不同情况下，时间复杂度有量级的差距，我们才会使用这三种复杂度表示法来区分。
均摊时间复杂度#
我们举一个例子：
// 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];
}
count = 1;//清空数组
array[0] = sum;
}
array[count] = val;
++count;
}
这段代码的代码逻辑是：首先，这个函数的基本功能是向一个整形数组中插入值。当数组满了之后，也就是 count == array.length 时，我们用 for 循环遍历数组求和，并清空数组，将求和之后的 sum 值放到数组 [0] 位置，然后再将要插入的 val 插入到 [count] 位置下。而当数组没有满的时候，也就是 count != array.length 时，直接将数据插入数组。
注意：此时清空数组的操作是置count为1。对于可反复读写的存储空间，使用者认为它是空的它就是空的。如果你定义空是指全部重写为0或者某个值，那也可以！使用者应只关心要存的新值。
那么，运用之前的三种时间复杂度的分析方法。
-
在最理想的情况下，数组中有空闲空间 (数组没有满)，我们只需要将数据插入到数组 [count] 的位置下即可。最好情况时间复杂度为 $O (1)$。
-
在最糟糕的情况下，数组没有空闲空间 (数组满了)，我们需要做一次遍历数组求和，然后再插入值。最坏情况时间复杂度为 $O (n)$。
-
其平均时间复杂度，我们可以通过概率论的方法分析。假设数组的长度是 n，根据数据插入的位置的不同，我们可以分为 n 种情况，每种情况的时间复杂度是 $O (1)$。除此之外，还有一种 “额外” 的情况，就是在数组没有空闲空间时插入一个数据，这个时候的时间复杂度是 $O (n)$。而且，这 n+1 种情况发生的概率是一样，都是 $1 \over
n+1$。所以，根据加权平均的计算方法，我们求得的平均时间复杂度就是：
3月18日，存疑。为什么左边是 2n / n+1 。。。但是也可以算作O(n)啊？真的搞不懂。。。
3月19日，答疑。最后去Leetcode上请教大佬，大佬的说法是：“2n/(n+1)，上下的数量级为n，可以看成2n/n = 2，时间复杂度是常量级，所以为O(1)。”，看完简直醍醐灌顶，茅塞顿开！
那么实际上，我们不需要那么复杂地求这个例子的平均复杂度。我们可以通过对比 find () 和 insert () 这两个例子来看一看。
首先，find () 函数在极端情况下，复杂度才为 $O (1)$。但 insert () 函数在大部分情况下，时间复杂度都为 $O (1)$，只有在个别情况下，复杂度才比较高，为 $O (n)$。这是 insert ()第一个区别于 find () 地方。
第二。对于 insert () 函数来说，O (1) 时间复杂度的插入和 O (n) 时间复杂度的插入，出现的频率是有规律可循的，有一定的前后时序关系。一般都是在 n-1 个 O (1) 的插入操作之后 (数组未满时插入数据)，紧跟着一个 O (n)(数组满时遍历求和，清空数组)，循环往复。
所以，针对这样一种特殊场景的复杂度分析，我们引入了一种更加简单的分析方法：摊还分析法，通过摊还分析得到的时间复杂度叫均摊时间复杂度。
通过例子来说明的话。每一次 O (n) 的插入操作，都会跟着 n-1 次 O (1) 的插入操作，所以耗时多的那次操作均摊到接下来的 n-1 次耗时少的操作上，均摊下来，这一组连续的操作的均摊时间复杂度就是 O (1).
平均时间复杂度和均摊时间复杂度的应用场景#
对一个数据结构进行一组连续操作时，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一起分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。
均摊时间复杂度就是一种特殊的平均时间复杂度
内容小结#
几个复杂度分析相关的概念，分别有：最好情况时间复杂度、最坏情况时间复杂度、平均时间复杂度、均摊时间复杂度。之所以引入这几个复杂度概念，是因为，同一段代码，在不同输入的情况下，复杂度量级有可能是不一样的 。在引入这几个概念之后，可以更加全面地表示一段代码的执行效率。
课后思考题目#
// 全局变量，大小为10的数组array，长度len，下标i。
int array[] = new int[10];
int len = 10;
int i = 0;
// 往数组中添加一个元素
void add(int element) {
if (i >= len) { // 数组空间不够了
// 重新申请一个2倍大小的数组空间
int new_array[] = new int[len*2];
// 把原来array数组中的数据依次copy到new_array
for (int j = 0; j < len; ++j) {
new_array[j] = array[j];
}
// new_array复制给array，array现在大小就是2倍len了
array = new_array;
len = 2 * len;
}
// 将element放到下标为i的位置，下标i加一
array[i] = element;
++i;
}
这段代码的逻辑是：往数组中添加一个元素，当数组未满时，直接插入；当数组满时，申请一个 2 倍大小的数组空间，并把原数组中的数据遍历传递给新数组，最后新数组复制给愿数组，替代它。
在这段代码中，最好时间复杂度：是当数组未满时，直接插入。为 O (1);
最坏时间复杂度：是当数组满时，需要遍历传递数组。为 O (n);
平均时间复杂度：根据插入位置的不同 ，会有 n 种情况。另外，数组满时也有一种情况，而每种情况的概率都为 $1 \over n+1$。最后复杂度为 O (1);
均摊时间复杂度：每 n 个 O (1) 操作后都会紧跟一个 O (n) 操作，有时序关系，且可均摊，所以均摊时间复杂度为 O (1)。