javascript的array.indexOf的时间复杂度是多少？

Question

indexOf 只是遍历数组还是做一些更快的事情？我知道这是依赖于实现的，但是Chrome或Firefox有什么作用？

Answer 1

查找与未排序数组中的值匹配的第一个索引的最有效方法是按顺序浏览列表，即 O(n(。MDN 也有一些提示：

返回

可以在数组中找到给定元素的第一个索引，如果该元素不存在，则返回 -1。

[...]

从索引

默认值：0(搜索整个数组(
要开始搜索的索引。如果索引大于或等于数组的长度，则返回 -1，这意味着不会搜索数组。如果提供的索引值为负数，则将其视为数组末尾的偏移量。注意：如果提供的索引为负数，则仍从前到后搜索数组。如果计算出的索引小于 0，则将搜索整个数组。

如果您想知道，以下是 WebKit 的实现方式：

EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState* exec)
{
    // 15.4.4.14
    JSObject* thisObj = exec->hostThisValue().toThis(exec, StrictMode).toObject(exec);
    unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
    if (exec->hadException())
        return JSValue::encode(jsUndefined());
    unsigned index = argumentClampedIndexFromStartOrEnd(exec, 1, length);
    JSValue searchElement = exec->argument(0);
    for (; index < length; ++index) {
        JSValue e = getProperty(exec, thisObj, index);
        if (exec->hadException())
            return JSValue::encode(jsUndefined());
        if (!e)
            continue;
        if (JSValue::strictEqual(exec, searchElement, e))
            return JSValue::encode(jsNumber(index));
    }
    return JSValue::encode(jsNumber(-1));
}

Answer 2

由于无法保证数组中项目的性质或顺序，因此您不能比 O(n( 做得更好，因此它会遍历数组。即使它是在CPU之间并行化实际搜索(不知道Firefox或chrome是否这样做，但它们可以(，它也不会改变有限数量的CPU的时间复杂度。

Answer 3

在 ECMA6 中，您有 Set() ，然后您可以执行以下操作：

var obj = new Set();
obj.add(1);
obj.has(1) === true;
obj.has(2) === false;

has的性能为 O(1(。