时间复杂度（2）

1.最好情况复杂度

2.最坏情况复杂度

3.平均时间复杂度

4.均摊时间复杂度

实战

// 全局变量，大小为10的数组array，长度len，下标i。
    int array[] = new int[10];
    int len = 10;
    int i = 0;
<pre><code>// 往数组中添加一个元素
void add(int element) {
    if (i &gt;= len) { // 数组空间不够了
        // 重新申请一个2倍大小的数组空间
        int new_array[] = new int[len*2];
        // 把原来array数组中的数据依次copy到new_array
        for (int j = 0; j &lt; 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;
}

最好情况复杂度是 O(1)

假设初始长度是n

第一次插入是 n

第二次插入是 2n

第k次插入是

$2^k - ^1 * n$

最坏情况复杂度是 O(n),k是常数可以忽略

平均复杂度 我还没有想明白