最好时间复杂度、最坏时间复杂度、平均时间复杂度、均摊时间复杂度

代码：

// 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;
}

一、最好时间复杂度

最好情况就是，arrary数组的第一个元素就是要查找的x，所以最好时间复杂度就是O(1)。

二、最坏时间复杂度

最坏的情况就是，这个数组中没有查找的这个元素，那么它会把这个数组遍历一遍，所以最坏时间复杂度是O(n)。

三、平均时间复杂度

 平均时间复杂度只有在特殊时候才会使用。以上面的代码为例分析：

一共有n + 1种情况，即从0~n，和不在数组中。

平均时间复杂度：

去掉系数、低阶、常数，平均时间复杂度就为O(n)。

四、均摊时间复杂度

均摊时间复杂度的情况更特殊，并不常用到。

思想是：将耗时最多的那次操作均摊到其他耗时最少的操作上。