JavaScriptオブジェクトキーを検索する時間の複雑さは何ですか？

Question

JavaScriptオブジェクトを辞書として使用しており、大文字と小文字を区別しないようにする必要がありました。私はこれを実装するためにObject.defineProperty()を使用：

Object.defineProperty(Object.prototype, "getKeyUpperCase", { 
    value: function(prop) { 
     for (var key in this) { 
      if (key.toUpperCase() === prop.toUpperCase()) { 
       return this[key]; 
      }; 
     }; 
    }, 
    enumerable: false 
}); 

JavaScriptでキーを経由してオブジェクトを検索する時の複雑さとは何ですか？私は約100万の鍵を保持する辞書を期待しています。

私には、最悪の場合はO(n)、最善のケースはO(1)、平均の場合はO(n/2)と思われます。これは正しいです？

オブジェクトのキーを配列（Object.Keys(dictionary).map(function(key) return key.toUpperCase()).sort()）として取得して、キーが存在するかどうかを確認する方が効率的でしょうか？この操作の平均時間複雑度がO(log n)であるということを訂正しますか？辞書の

使い方は、この線に沿っている：

Answer 1

まず、ビッグO記法に関するいくつかの考え：

この数学的なツールは「桁」の概念をつかむしようとします長期的なシナリオでは、サイズが大きくなるにつれて、定数はますます小さくなります。したがって、通常はbig-Oを計算することは定数を気にしません。

これがO（n/2）= O（n）の理由です。

したがって、線形ルックアップにはO（n）時間の複雑さがあります。ソートについて

：

のJavaScriptのソートアルゴリズムは、ブラウザに依存しているが、あなたはそのためのO（N Nをログ）複雑さをとることができます。通常、1つの検索のみをソートする価値はありませんが、1回だけソートできれば、それは価値があるかもしれません。ちなみに、並べ替えられたリストを検索する場合は、検索のスピードを上げるためにバイナリ検索を実装しようとする可能性があります。