Ruby 的 Array#insert 的复杂度是多少？

Question

Ruby 的 Array#insert 的复杂度是多少？

是 O(1) 还是 O(n)（内存被复制）？

Answer 1

简单的基准测试表明插入是O(n)：

Benchmark.bm do |x|
  arr = (1..10000).to_a
  x.report { 10000.times {arr.insert(1, 1)} }
  arr = (1..100000).to_a
  x.report { 10000.times {arr.insert(1, 1)} }
  arr = (1..1000000).to_a
  x.report { 10000.times {arr.insert(1, 1)} }
end

     user     system      total        real
 0.078000   0.000000   0.078000 (  0.077023)
 0.500000   0.000000   0.500000 (  0.522345)
 5.953000   0.000000   5.953000 (  5.967949)

只要你不推到数组的末尾，当它变成O(1)：

Benchmark.bm do |x|
  arr = (1..10000).to_a
  x.report { 10000.times {arr.push 1} }
  arr = (1..100000).to_a
  x.report { 10000.times {arr.push 1} }
  arr = (1..1000000).to_a
  x.report { 10000.times {arr.push 1} }
  arr = (1..10000000).to_a
  x.report { 10000.times {arr.push 1} }
end

   user     system      total        real
 0.000000   0.000000   0.000000 (  0.001002)
 0.000000   0.000000   0.000000 (  0.001000)
 0.000000   0.000000   0.000000 (  0.001001)
 0.000000   0.000000   0.000000 (  0.002001)