Сложность javascript indexOf метод

Question

Я изучал большое обозначение O для технического интервью, а затем понял, что метод javascript indexOf может иметь временную сложность O (N), когда он проходит через каждый элемент массива и возвращает индекс где его нашли.

Мы также знаем, что временная сложность O (n^2) (n квадрата) не является хорошим показателем эффективности для больших данных.

Так что это плохая идея использовать indexOf внутри петель? В javascript его общий вид, где код indexOf используется внутри циклов, может быть для измерения равенства или для подготовки некоторого объекта.

Вместо того, чтобы массивы, мы предпочитаем объекты везде, где это необходимо, поскольку они обеспечивают поиск с постоянной производительностью времени O (1).

Любые предложения будут оценены.

Answer 1

Это может быть плохой идеей использовать IndexOf внутри петли особенно если структура данных вы ищете через довольно большой. Для этого нужно иметь хеш-таблицу или словарь, содержащий индекс каждого элемента, который вы можете генерировать в O (N), путем циклического перехода по структуре данных и обновления при каждом добавлении в структуру данных.

Если вы нажать что-то на конец структуры данных потребуется O (1) время обновить эту таблицу и наихудший сценарий, если вы толкаете что-то в начале структуры данных она будет принять O (N).

В большинстве случаев это будет стоить того, чтобы получить индекс O (1) Время.

Answer 2

Будьте честным, tl; dr. Но я сделал несколько тестов скорости различных способов проверки вхождения в строку (если это ваша цель использовать indexOf. Если вы на самом деле пытаетесь получить позицию матча, я лично не знаю, как помочь вы там). Пути я Испытывали:

• .includes()
• .match()
• .indexOf()

(Есть также варианты, такие как .search(), .lastIndexOf() и т.д. Те, я не проверял).

Вот тест:

var test = 'test string'; 
 

 
console.time('match'); 
 
console.log(test.match(/string/)); 
 
console.timeEnd('match'); 
 

 
console.time('includes'); 
 
console.log(test.includes('string')); 
 
console.timeEnd('includes'); 
 

 
console.time('indexOf'); 
 
console.log(test.indexOf('string') !== 0); 
 
console.timeEnd('indexOf');

Я знаю, что они не являются петли, но показать вам, что все в основном с той же скоростью. И честно говоря, каждый делает разные вещи, в зависимости от того, что вам нужно (вы хотите выполнить поиск по RegEx? Вам нужно быть совместимым с ECMAScript 2015? И т. Д. - я даже не перечислял их всех), действительно ли необходимо проанализировать это так много?

Из моих тестов иногда выигрывал indexOf(), иногда один из них выигрывал.