[解決済み] Javascript ES6 コレクションの計算/時間複雑性

質問

ES6仕様のキー付きコレクション（Set、Map、WeakSet、WeakMap）には、どのような時間複雑性（big-O記法）がありますか？

私の予想、そしてほとんどの開発者の予想では、仕様と実装が 広く受け入れられている 性能の良いアルゴリズムを使用することであり、その場合 Set.prototype.has , add と delete は平均的な場合、すべてO(1)になる。についても同様に Map と Weak– と同等です。

実装の時間的複雑さが義務付けられたかどうかは、私にはまったくわかりません。 ECMAScript 2015 言語仕様 - 第 6 版 - 23.2 セットオブジェクト .

私が誤解していなければ (誤解している可能性も大いにありますが)、ECMA の仕様では、実装 (たとえば Set.prototype.has など) は線形時間 ( O(n) ) アルゴリズムを使用することです。より高性能なアルゴリズムが仕様で義務付けられていない、あるいは許可されていないのは非常に驚くべきことであり、なぜそうなのかの説明に非常に興味があります。

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

右から という段落があり、その にリンクされています。

セットオブジェクトは、平均してコレクション内の要素数に対してサブリニアなアクセス時間を提供する [メカニズム] を用いて実装されなければならない。

にも同じ文章があります。 地図 , 弱いマップ と 弱いセット .

ECMAの仕様では、実装(Set.prototype.hasなど)はリニアタイム(linear time)を使うことが義務付けられているようですね。 O(n) ) アルゴリズムを使用することを義務付けているようです。

いいえ。

この中で使われているデータ構造 Set オブジェクトの仕様は、セットオブジェクトの要求される観察可能なセマンティクスを記述することのみを目的としています。実行可能な実装モデルであることは意図していません。

観測可能なセマンティクスは、ほとんどが予測可能な反復順序に関連するものです（これは、まだ 効率的かつ高速に実装できる ). 実装では、ハッシュ テーブルまたは一定のアクセスを持つ同様のものを使用することが仕様で期待されていますが、(対数のアクセス複雑度を持つ) 木も同様に許可されています。