ruby - 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)