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

// 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) 最好情况下是直接可以插入数据：O(1)
(2) 最坏情况下是数组已经满了，开辟一个两倍的数组，并循环之前的数组赋值给新数组：第一次循环为10、第二次循环为210、第三次循环为410、....、第n次循环为102^{n-1。去掉常数系数后。最坏时间复杂度为O(2}n)
(3) 平均加权时间复杂度：第一次循环前 有10个O(1)的情况、 第二次循环前 有10-1个O(1) 的情况、 第三次循环前 有 210-1 个 O(1) 的情况、第四次循环前 有 2^210-1 个O(1) 的情况 ......第n次循环前 有2^(n-1)10-1个O(1) 的情况，加上数组已满的情况 共有2^(n-1)10 种可能，每个可能的概率为 1/2^(n-1)10。1/2^(n-1)10 + 1/2^(n-1)10 + 1/2^(n-1)10 + .... + 1/2^(n-1)10 + 2^n10 / 2^(n-1)10 时间复杂度为O(1)
(4) 因为前后有时序关系，所以可以用均摊分析来分析，最坏情况时间复杂度为O(2^n) 分给 2^(n-1)个最好情况时间复杂度O(1) 结果还是O(1).