[시간복잡성] indexOf(), hash변환 후 값 추출

코테를 풀다가, indexOf() 를 사용해 시간초과가 나던 부분을

전체 배열을 {배열의 값: index, ...} 형태의 hash로 변환하고 값을 추출하는 식으로 변경해서 풀게 되었다.

그렇다면 시간 차이가 얼마나 나는가. 그리고 배열의 길이가 얼마나 짧아야 indexOf()가 유리할까?

 

모의 배열을 하나 생성해서, 아래 두 가지의 경우를 조사해본다. 

시간 소요는 <cod>window.performance.now();</cod> 를 사용해서 구했다.

1.배열.indexOf("문자열") 출력

2. 각 위치를 hash로 전부 변환하고 특정 값의 위치 출력 ( ex. {값1 : 0 , 값2 :1, 값3: 2 ... )

테스트할 배열은 그냥 for문으로 임의로 만들었다. 길면 길수록 뽑기가 힘들었다.. 실행은 10번 정도를 하고 평균값을 구했다. (사실 좀 모자랐던 것 같다)

임의로 만든 테스트 배열

 

배열의 길이가 100일때

배열을 2번Hash 형태로 변환하는데 든 시간 : 평균 1.27

/	평균	최소시간	최대시간
배열.indexOf(99번째)	4.02	3.9	4.1
배열.indexOf(10번째)	3.9	3.9	4.1
해시[99번째]	4.24	3.9	5.2
해시[10번째]	4.03	3.8	4.1

 

그렇게 크게 차이도 안나는데.. 오히려 Hash 로 변환하는 시간까지 생각하면 더 오래 걸린 편.

그렇다면 배열 길이를 프로그래머스 최대 길이와 동일하게 1,000,000 로 한다면?

 

배열의 길이가 1,000,000일때

배열을 2번Hash 형태로 변환하는데 든 시간 : 평균 267.26

/	평균	최소시간	최대시간
배열.indexOf(999999번째)	6.79	6.1	7.8
배열.indexOf(999999번째)	4.62	4.3	5.0
해시[ 999999번째]	5.14	4.3	7.6
해시[10번째]	4.54	3.9	4.8

 

 

결론은 진짜 모르겠다. 비슷비슷한데..알고리즘을 제대로 알면 알게될까 ㅠㅠㅠ