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

用法是沿着这个线路：

只需要记下你不需要搜索每个键......你只会测试所有可能的单个键的情况，即'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）的该复杂性。通常，只有一次查找就不值得排序，但是如果只能排序一次，并且可以进行多次查找，那么这可能是值得的。顺便说一句，如果你有一个排序列表进行搜索，也许你可以尝试执行二进制搜索来加速你的搜索。

搜索JavaScript对象键的时间复杂度是多少？

相关推荐