arrays - 从数组中删除元素的复杂度是多少？

Question

从数组中删除元素的时间复杂度是多少？具体来说，使用 array.pop 删除最后一个元素时的复杂度是多少？ ？

Answer 1

它的O(1)。

来源:array.c

VALUE
rb_ary_pop(VALUE ary)
{
  long n;
  rb_ary_modify_check(ary);
  n = RARRAY_LEN(ary);
  if (n == 0) return Qnil;
  if (ARY_OWNS_HEAP_P(ary) && 
      n * 3 < ARY_CAPA(ary) &&
      ARY_CAPA(ary) > ARY_DEFAULT_SIZE)
  {
    ary_resize_capa(ary, n * 2);
  }
  --n;
  ARY_SET_LEN(ary, n);
  return RARRAY_AREF(ary, n);
}

正如您所看到的，它只是减少数组的长度并返回该索引处的值。有时，弹出可能会触发调整大小，时间复杂度为 O(n)