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

这是我在一个课程里看到的例子，假如说调用 n 次 add 方法，最好时间复杂度、最坏时间复杂度和平均时间复杂度分别是多少？

下面这个是课程评论中的一个答案，讲师也说是对的：

1. 最好情况时间复杂度为 O(1)

2. 最坏情况分析：

   最坏情况代码执行的次数跟每次数组的长度有关

   第 1 次调用 add 的执行的次数为 n ,

   第 2 次调用 add 的执行的次数为 2n ,

   第 3 次调用 add 的执行的次数为 2^2 * n

   第 k 次调用 add 的执行的次数为 2^(k-1) * n

   最坏时间复杂度为 O(n)。

3. 平均情况分析 当每次遇到最坏情况时数组会进行 2 倍扩容，原数组被导入新数组，虽然数组的长度变大了，但是插入操作落在的区间的长度是一样的，分别是 0~len-1, len~(2len-1), ….；

   插入的情况仍是 len+1 种：0~len-1 和插满之后的 O(len)；

   所以每次插入的概率是：p= 1/len+1，

   最后求出加权平均时间复杂度为 1*p + 2*p+ ▪▪▪ + len * p + len * p = O(1) ;

4. 均摊时间复杂度 O(1)

5. 而均摊复杂度由于每次 O(len) 的出现都跟着 len 次 O(1)，是前后连贯的，因而将 O(len) 平摊到前 len 次上，得出平摊复杂度是 O(1)

但是按我的理解：

• 最坏情况分析：

  最坏情况代码执行的次数跟每次数组的长度有关

  第 1 次调用 add 的执行的次数为 2^0 * 10,

  第 2 次调用 add 的执行的次数为 2^1 * 10 ,

  第 3 次调用 add 的执行的次数为 2^2 * 10

  第 n 次调用 add 的执行的次数为 2^(n-1) * 10 = 2^n * 5

  常系数可以省略，所以调用 n 次 add 方法的最差时间复杂度应该时 2^n。

我看课程评论里面都把数组的长度假设为 n，但是数组的初始长度明明是 10，这样假设的话跟上面的代码根本就不是一个意思了。我觉得 n 应该是调用 add 的次数才对。

大家怎么看？

大佬有話說 (0)