javascript 的array.indexOf 的时间复杂度是多少？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/19287033/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
What is the time complexity of javascript's array.indexOf?
提问by user1056805
Does indexOf simply walk through the array or does it do something that is faster? I know that this is implementation dependent but what does Chrome or Firefox do?
indexOf 是简单地遍历数组还是执行更快的操作？我知道这取决于实现，但 Chrome 或 Firefox 是做什么的？
回答by Brendan Long
The most efficient way to find the first index matching a value in an unsorted array is to just walk through the list in order, which is O(n). MDNalso has some hints:
在未排序数组中找到匹配值的第一个索引的最有效方法是按顺序遍历列表，即 O(n)。MDN也有一些提示：
Returns the first indexat which a given element can be found in the array, or -1 if it is not present.
[...]
fromIndex
Default: 0 (Entire array is searched)
The index to start the search at. If the index is greater than or equal to the array's length, -1 is returned, which means the array will not be searched. If the provided index value is a negative number, it is taken as the offset from the end of the array. Note: if the provided index is negative, the array is still searched from front to back. If the calculated index is less than 0, then the whole array will be searched.
返回可以在数组中找到给定元素的第一个索引，如果不存在，则返回 -1。
[...]
从索引
默认值：0（搜索整个数组）
开始搜索的索引。如果索引大于或等于数组的长度，则返回-1，这意味着不会搜索数组。如果提供的索引值为负数，则将其视为距数组末尾的偏移量。注意：如果提供的索引为负数，仍然从前到后搜索数组。如果计算出的索引小于 0，则将搜索整个数组。
In case you're wondering, here's how WebKit implements it:
如果您想知道，以下是 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));
}
回答by triggerNZ
With no guarantees about the nature or order of items in an array, you cannot do better than O(n), so it would walk through the array. Even if it was to parallelise the actual search across CPUs (no idea if firefox or chrome do this, but they could), it does not change the time complexity with a finite number of CPUs.
由于不能保证数组中项目的性质或顺序，你不能做得比 O(n) 更好，所以它会遍历数组。即使它是跨 CPU 并行化实际搜索（不知道 firefox 或 chrome 是否这样做，但他们可以），它也不会改变有限数量的 CPU 的时间复杂度。
回答by Matheus Pavin
In ECMA6, you have the Set(), and then you can do:
在 ECMA6 中，您拥有Set(), 然后您可以执行以下操作：
var obj = new Set();
obj.add(1);
obj.has(1) === true;
obj.has(2) === false;
The performance of hasis O(1).
的性能has是 O(1)。
