[解決済み] JavaScript 配列のビッグ・オー

質問

JavaScriptの配列は、項目を追加したり削除したりすることで、非常に簡単に変更することができます。これは、ほとんどの言語の配列が固定サイズであり、サイズを変更するために複雑な操作を必要とするという事実を多少覆い隠します。JavaScriptは性能の悪い配列のコードを簡単に書くことができるようです。これが疑問につながっています。

配列のパフォーマンスに関して、JavaScript の実装からどのようなパフォーマンス (大きな O 時間複雑性の観点から) を期待できますか？

すべての合理的なJavaScriptの実装は、最大で以下のようなビッグOを持つと仮定します。

• アクセス - O(1)
• 追加 - O(n)
• プリペンド - O(n)
• 挿入 - O(n)
• 削除 - O(n)
• スワッピング - O(1)

JavaScript では、あるサイズまで配列をあらかじめ埋めておくことができます。 new Array(length) 構文で指定します。(ボーナス質問。この方法で配列を作るのは O(1) なのか O(n) なのか？） これは従来の配列に近いもので、あらかじめ大きさを決めておけば、O(1)の追加を可能にします。循環バッファのロジックを追加すれば、O(1)のプリペンドが実現できます。動的に拡張される配列が使用される場合、O(log n)はどちらも平均的なケースとなるでしょう。

ここでの仮定よりも、あるものについてはより良いパフォーマンスを期待できますか? どの仕様にも概要が書かれていないので何も期待していませんが、実際には、すべての主要な実装が舞台裏で最適化された配列を使用している可能性があります。動的に拡張する配列やその他のパフォーマンスを向上させるアルゴリズムが動作しているのでしょうか？

追伸

私がこれを疑問に思っている理由は、いくつかのソートアルゴリズムを研究しているからです。そのほとんどは、それらの全体の大きなOを記述するときに、追加と削除がO(1)の操作であると仮定しているようです。

どのように解決するのですか?

_{注：この答えは2012年には正しかったのですが、今日のエンジンはオブジェクトと配列の両方に対して非常に異なる内部表現を使用しています。この回答は正しいかもしれませんし、正しくないかもしれません。}

ほとんどの言語が配列を実装しているのとは対照的に、Javascriptでは配列はオブジェクトであり、値は通常のオブジェクトの値と同様にハッシュテーブルに格納されます。そのため

• アクセス - O(1)
• 追加 - 平均O(1) (ハッシュテーブルのリサイズが必要な場合もあるが、通常は挿入のみ)
• プリペンド - O(n) via unshift を介して、すべてのインデックスを再割り当てする必要があるため、O(n)です。
• 挿入 - 値が存在しない場合、償却 O(1)。既存の値をシフトしたい場合は O(n)。 splice ).
• 削除 - 値を削除するには償却 O(1)、インデックスを再割り当てする場合は O(n) で splice .
• スワッピング - O(1)

一般的に、dict の任意のキーの設定または解除は O(1) で償却され、インデックスが何であるかにかかわらず、配列についても同じことが言えます。既存の値の番号を変更する必要がある操作は、影響を受けるすべての値を更新する必要があるため、単純に O(n) となります。