javascript - 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)。