자바 스크립트 indexOf 메서드의 시간 복잡도

Question

기술적 인 인터뷰에서 큰 O 표기법을 공부 한 다음 자바 스크립트의 indexOf 메서드가 배열의 각 요소를 통과하여 색인을 반환 할 때 O (N)의 시간 복잡성을 가질 수 있음을 깨달았습니다. 발견 된 곳.

또한 O (n^2) (n^2)의 시간 복잡성은 더 큰 데이터에 대한 좋은 성능 척도가 아니라는 것을 알고 있습니다.

루프 내부에 indexOf을 사용하는 것은 나쁜 생각입니까? 자바 스크립트에서 루프 내에서 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()가 이기고, 다른 하나가 이기기도합니다.