String.prototype.indexOf의 시간 복잡도

[innerstella]

indexOf(검색할 문자열, fromIndex)

• 인자로 fromIndex를 받았을 경우에 해당 인덱스부터 탐색을 시작해서 해당 값을 return
• fromIndex를 받지 않았을 경우에는 0번 인덱스부터 순차적으로 탐색을 시작하며 찾을 경우 값을 return
• 시간 복잡도 : $O(n)$ 선형 탐색
  • 이론적으로는 이진 탐색보다 속도가 느리지만, 실 사용 케이스에 따라 다름
  • 정렬되지 않은 데이터에 대해 사용
  • 길이가 길수록 비효율적

이진 탐색 시간 복잡도 : $O(logN)$

• 중간을 기준으로 탐색 대상을 절반씩 줄여나감
• 효율 조건 : 정렬된 데이터

따라서, 정렬되지 않은 배열의 길이가

• 짧을 때 → 선형 탐색 효율적 (& 메모리 액세스 오버헤드 감소)
• 길 때 → 이진 탐색 효율적