搜索 JavaScript 对象键的时间复杂度是多少? [英] What is the time complexity of searching JavaScript object keys?

问题描述

我使用 JavaScript 对象作为字典，并希望使键不区分大小写.我使用 Object.defineProperty() 来实现:

I am using a JavaScript object as a dictionary, and wanted to make keys case-insensitive. I used Object.defineProperty() to implement this:

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 万个键.

What is the time complexity of searching an object via key in JavaScript? I'm expecting the dictionary to hold around 1 million keys.

对我来说，最坏的情况是 O(n)，最好的情况是 O(1)，平均情况是 O(n)/2).这是正确的吗?

To me it looks like worst case would be O(n), best case would be O(1) and average case would be O(n/2). Is this correct?

以数组形式检索对象的键是否会更有效(Object.Keys(dictionary).map(function(key) return key.toUpperCase()).sort())检查密钥是否存在?我说这个操作的平均时间复杂度是 O(log n) 是否正确?

Would it be substantially more efficient to retrieve the object's keys as an array (Object.Keys(dictionary).map(function(key) return key.toUpperCase()).sort()) to check if the key exists? Am I correct in saying that the average time complexity of this operation is O(log n)?

字典的用法是这样的:

var dictionary = {/* some million keys or so */};
var oldKey = someSmallArray[i];
var newValue = dictionary.getKeyUpperCase(oldKey.trim().toUpperCase());

推荐答案

首先，对 big-O 表示法的一些思考:

First, some thought about big-O notation:

这个数学工具试图在长期场景中抓住数量级"的概念.随着规模的增长，常数变得越来越不重要.因此计算 big-O 通常我们不会打扰常量.

This mathematical tool tries to grab the concept of "order of magnitude" in a long-term scenario. As size grows constants get less and less importance. Hence calculating big-O usually we don't bother with constants.

这就是为什么 O(n/2) = O(n).

That's why O(n/2) = O(n).

所以线性查找的时间复杂度为 O(n).

So the linear lookup has O(n) time complexity.

关于排序:

JavaScript 的排序算法依赖于浏览器，但您可以假设它的复杂度为 O(n log n).通常，仅对一次查找进行排序是不值得的，但是如果您只能排序一次并且可以进行多次查找，那么这可能是值得的.顺便说一句，如果你有一个排序列表要搜索，也许你可以尝试实现二分搜索来加快搜索速度.

The sort algorithm of JavaScript is browser dependent but you can assume an O(n log n) complexity for that. Usually, it doesn't worth to sort for only one lookup but if you can sort only once and you can make several lookups maybe it is worth it. By the way, If you have a sorted list to search maybe you could try to implement binary search to speed up your searching.

这篇关于搜索 JavaScript 对象键的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！