时间复杂度分析

用几种分析方法分析下面函数的时间复杂度

// 全局变量，大小为10的数组array，长度len，下标i。int array[] = new int[10]; int len = 10;int i = 0;void add(int element) {if (i >= len) {// 数组空间不够了int new_array[] = new int[len*2];for (int j = 0; j < len; ++j) {new_array[j] = array[j];}array = new_array;len = 2 * len;}// 将element放到下标为i的位置，下标i加一array[i] = element;++i;}

首先，简单分析一下这个函数，很明显这是一个往数组中插入元素的函数方法。当数组元素不够时，重新开辟一个2倍于原数组大小的数组空间，把原来array数组中的数据循环遍历到new_array数组中，再把new_array复制给array，最后将待插入的element放到下标为i的位置，下标i加一，完成操作。

下面来分析它的时间复杂度:

最好情况分析

当i < len时，即 i = 0,1,2,…,n-1的时候，不需要走for循环操作，即可以直接插入元素，因此最好情况时间复杂度为 O(1)。最坏情况分析：

当i >= len时, 即 i = n的时候，需要走for循环操作，因此最坏时间复杂度为 O(nnn)。平均情况分析

当每次遇到最坏情况时数组会进行2倍扩容，原数组被导入新数组，虽然数组的长度变大了，但是插入操作落在区间的长度是一样的，分别是0到n-1，n到2n-1…插入的情况仍是n+1种：0到n-1都是O(1)和插满之后的O(nnn)；

所以每次插入的概率p=1/(n+1)p= 1/(n+1)p=1/(n+1)，最后求出加权平均时间复杂度为1∗p+1∗p+...+1∗p+n∗p=2n/(n+1)=O(1)1*p + 1*p+ ... + 1*p + n*p =2n/(n+1)= O(1)1∗p+1∗p+...+1∗p+n∗p=2n/(n+1)=O(1);摊还分析

可以发现，每出现一次最坏情况的O(nnn)，就会出现n-1次O(1)，可以把每一次O(nnn)时间复杂度，用后面的 n-1 次 O(1) 均摊，可以得到均摊时间复杂度O(1)。