Какова временная сложность javascript array.indexOf?

Ответ 1

Самый эффективный способ найти первый индекс, соответствующий значению в несортированном массиве, - просто пройти по списку по порядку, то есть O (n). MDN также имеет некоторые подсказки:

Возвращает первый индекс, в котором данный элемент может быть найден в массиве, или -1, если он отсутствует.

[...]

fromIndex

По умолчанию: 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));
}

Ответ 2

Без каких-либо гарантий относительно характера или порядка элементов в массиве вы не можете сделать лучше, чем O (n), поэтому он будет проходить через массив. Даже если бы это было для параллельного фактического поиска по процессорам (не знаю, делают ли firefox или chrome это, но могут), это не меняет сложность времени с конечным числом процессоров.

Ответ 3

В ECMA6 у вас есть Set(), а затем вы можете сделать:

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

Производительность has O (1).