Złożoność czasowa indeksu javascriptJeśli chodzi o metodę

Question

Studiowałem napis Big O w celu przeprowadzenia wywiadu technicznego, a następnie zdałem sobie sprawę, że metoda javascripta indexOf może mieć złożoność czasową O (N), ponieważ przechodzi przez każdy element tablicy i zwraca indeks gdzie ją znaleziono.

Wiemy również, że złożoność czasowa O (n^2) (n kwadrat) nie jest dobrym miernikiem wydajności dla większych danych.

Czy używanie wewnętrznych pętli indexOf jest złym pomysłem? W javascriptie powszechne jest używanie kodu wewnątrz metody, w którym używana jest metoda indexOf, aby zmierzyć równość lub przygotować jakiś obiekt.

Zamiast tablic, powinniśmy preferować obiekty, w razie potrzeby, ponieważ zapewniają one wyszukiwanie o stałej wydajności O (1).

Wszelkie sugestie zostaną docenione.

Answer 1

To może być zły pomysł, aby użyć indexOf wewnątrz pętli zwłaszcza jeśli datastructure jesteś przeszukując jest dość duży. Jednym z zadań jest posiadanie tablicy mieszającej lub słownika zawierającego indeks każdego elementu, który można wygenerować w czasie O (N), przechodząc przez strukturę danych i aktualizując ją za każdym razem, gdy dodajesz strukturę danych.

Jeśli pchasz coś na koniec struktury danych zajmie O (1) czas, aby zaktualizować ten stół i najgorszy scenariusz jest, jeśli wcisnąć coś na początek struktury danych to będzie wziąć O (N).

W większości scenariuszy będzie warto, ponieważ uzyskanie indeksu będzie O (1) Czas.

Answer 2

Szczerze mówiąc, tl; dr. Ale zrobiłem kilka testów prędkości różnych sposobów sprawdzania występowania w ciągu znaków (jeśli jest to twoim celem używania indexOf. Jeśli faktycznie próbujesz uzyskać pozycję meczu, ja osobiście nie wiem, jak pomóc ty tam). Sposoby testowałem były:

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

(Istnieją również odmiany, takie jak .search(), .lastIndexOf() itp tych, których nie testowałem).

Tutaj jest test:

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');

wiem, że nie są pętle, ale pokazać, że wszyscy są w zasadzie takie same prędkości. I szczerze mówiąc, każdy robi różne rzeczy, w zależności od tego, czego potrzebujesz (czy chcesz przeszukiwać wg RegEx? Czy musisz być kompatybilny z ECMAScript 2015? Itd. - nawet nie wymieniłem ich wszystkich) czy jest to naprawdę konieczne do analizy to tyle?

Z moich testów wygrał czasami indexOf(), czasem wygrał jeden z pozostałych.