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

我将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中的键搜索对象的时间复杂度是多少？我希望字典能容纳大约一百万个键。

在我看来，最坏的情况是O(n)，最好的情况是O(1)，平均情况是O(n/2)。它是否正确？

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

字典的用法与此类似：

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

最佳答案

首先，对大O表示法的一些思考：

这种数学工具试图在长期情况下抓住“数量级”的概念。随着大小的增长，常数变得越来越不重要。因此，计算big-O通常不会打扰常量。

这就是O（n / 2）= O（n）的原因。

因此，线性查找的时间复杂度为O（n）。

关于排序：

JavaScript的排序算法取决于浏览器，但是您可以为此假设O（n log n）复杂度。通常，仅进行一次查找就不值得进行排序，但是如果您只能进行一次排序并且可以进行多次查找可能就值得了。顺便说一句，如果您有要搜索的排序列表，则可以尝试实现二进制搜索以加快搜索速度。