最好、最坏情况时间复杂度
下面我们给出最好、最坏时间复杂度的定义：
最好时间复杂度：在最理想的情况下，执行这段代码的时间复杂度。
最坏时间复杂度：在最不理想，运气最坏的时候，执行这段代码的时间复杂度。
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;
}
}
return pos;
}
如上述代码所示：
- 最好情况下：数组array的第一个数据为要寻找的值x，那么最好时间复杂度就是O（1）。
- 最坏情况时间复杂度：直到循环到数组最后一个数据才与x相等。那么最坏时间复杂度就是O（n）。
平均复杂度
然而最好、最坏两种时间复杂度出现的情况都是很少见的。为了更好的评价一段代码的时间复杂度，我们引用平均复杂度这个概念。
平均复杂度的含义就和它的名字一样，是在平均情况下的复杂度。
它把每种情况下的复杂度加起来，然后除以情况的个数，所得的值就是平均复杂度，类似于数学上的均值。
还以上述代码为例，因为与我们输入值相同数据在数组中的位置是不固定且平均的，在每个位置上的概率都是。找到数据所需时间就为
那么平均复杂度公式为：
该公式考虑数组中不存在输入的数据这一特殊情况，因此多一个时间复杂度为的情况。
上述结果虽然是正确的，但是中间步骤是有瑕疵的，瑕疵就在于数组中不存在输入的数据这一情况。
在上述计算公式中，我们把数组不存在所需数据这一情况简化为数组中任意位置存在数据的情况，然而实际上则不是这样的。不存在数据应该与存在数据的所有情况的概率相同。因此上述公式就变化为：
均摊时间复杂度
int[] array = new int[n];
int count = 0;
void insert(int val){
if (count == array.length) {
int sum = 0;
//执行一段时间复杂度为O(n)的操作
for (int i = 0; i < array.length; i++) {
sum = sum + array[i];
}
array[0] = sum;
count = 1;
}
//执行时间复杂度为O(1)的操作
array[count] = val;
++count;
}
上述代码实现的是向数组里插入数据的功能。当数组未满的时候直接插入，如果数组已经满了。则遍历数组，求其元素之和，然后将其赋予数组第一个元素，然后再插入数据。虽然这个代码没什么意义，但是主要是为了实现注释中的操作。
最好时间复杂度为，最坏时间复杂度为
。
对上述代码进行平均时间复杂度的计算：
此代码与上面一个代码有如下区别：
- find()函数在极端情况下，时间复杂度才为
，而insert()函数则大多数情况下都为
。
- 对于insert()函数来说，
所以对于这种情况，我们不需要像计算平均时间复杂度一样，计算出每种情况的时间然后取加权平均值。
我们有一种特殊的方法：摊还分析法，使用该方法得出的时间复杂度叫做均摊时间复杂度。
具体分析过程如下：
每一次
对一个数据结构进行一组连续操作中，在满足上述两个区别的情况下，我们可以将这组操作放在一起分析。看是否能将复杂度较高的操作分摊到复杂度较低的操作上。而且，在能够应用均摊复杂度分析的场合，一般均摊时间复杂度就等于最优时间复杂度。
