搜索JavaScript對象鍵的時間複雜度是多少？

我正在使用JavaScript對象作爲字典，並且希望使鍵不區分大小寫。我以前Object.defineProperty()來實現這一點：搜索JavaScript對象鍵的時間複雜度是多少？

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)？字典的

用法是沿着這個線路：

來源

2017-09-24 Zach Smith

只需要記下你不需要搜索每個鍵......你只會測試所有可能的單個鍵的情況，即'this ['name']'vs this ['Name']'vs '這['NAme']'等等。此外，您可以使用字典中的[Proxy]（https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Proxy），而不是直接使用字典，以確保每個按鍵在設置時總是小寫/大寫/得到 –

謝謝。我沒有想到這一點。那會比我所做的更快嗎？我不知道如何在JavaScript中實現字典，所以我不知道如何比較性能 –

這取決於被測試的密鑰的長度。因爲您需要創建密鑰的每種可能情況，然後對其進行測試。而且這個數字本身可能會相當大。我個人會使用代理路由（如果使用支持的瀏覽器），因爲根本不會搜索，您只需在setter和getter中使用'this [key.toLowerCase（）]'。 –

首先，關於大O記法的一些想法：

這種數學工具試圖抓住的「量級」的概念在長期的情況下。隨着規模的增長，常數的重要性越來越小。因此，計算大O通常我們不打擾常數。

這就是爲什麼O（n/2）= O（n）。

所以線性查找具有O（n）時間複雜度。

關於排序：

的JavaScript的排序算法是依賴於瀏覽器，但你可以假設爲O（n log n）的該複雜性。通常，只有一次查找就不值得排序，但是如果只能排序一次，並且可以進行多次查找，那麼這可能是值得的。順便說一句，如果你有一個排序列表進行搜索，也許你可以嘗試執行二進制搜索來加速你的搜索。

來源

2017-09-24 14:36:54

搜索JavaScript對象鍵的時間複雜度是多少？

回答

相關問題