Runner in the High

技術のことをかくこころみ

JavaScriptにおける配列操作の計算量オーダー

日本語だとググっても出てこなかったのでまとめた

操作 計算量
検索 O(n)
添字アクセス O(1)
挿入(splice) O(n)
削除(splice) O(n)
削除(delete) O(1)
最後に追加 O(1)
先頭に追加 O(n)
スワップ O(1)

添字アクセスがO(1)だったりするのは、JavaScriptの配列は連結リストなどではなく単なるインデクスをキーで持つObjectだから。

ちなみにdeleteを使った削除というのはspliceと違って要素がundefinedと交換されるだけのものなので後続要素への走査が走らないためO(1)になる。

参考: https://stackoverflow.com/questions/11514308/big-o-of-javascript-arrays