⏳分析一下这段代码的时间复杂度

let array = new Array(10)
let len = 10
let i = 0

// 向数组中添加一个元素
function add(element) {
  // 数组空间不够了
  // 重新申请一个2倍大小的数组空间
  if (i >= len) {
    // 把原来array数组中的数据依次copy到new_array
    let new_array = new Array(len * 2)
    for (let 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
}

分析：

• 当 i < len 时，即 i = 0,1,2...n-1 的时候，不走 for 循环，所以这 n 次的时间复杂度都是 O(1)
• 当 i >= len 时，即 i = n 的时候，需要走 for 循环拷贝 array 到 new_array，所以这 1 次的时间复杂度是 O(n)

由此可知：

• 最好情况时间复杂度 (best case time complexity) 为 O(1)

• 最坏情况时间复杂度 (worst case time complexity) 为 O(n)

• 平均情况时间复杂度 (average case time complexity)

  • 方法一：

    所以时间复杂度为 O(n)

    注：1+1+...+1 中有 n 个 1

  • 方法二（加权平均法，也称期望）：

    所以时间复杂度为 O(n)

    注：1*(1/n+1)+1*(1/n+1)+...+1*(1/n+1) 中有 n 个 1*(1/n+1)

  • 方法三（均摊时间复杂度）：

    前 n 个操作复杂度都是 O(1)，第 n+1 次操作的复杂度是 O(n)，所以把最后一次的复杂度分摊到前 n 次上，那么均摊下来每次操作的复杂度为 O(1)