[JS] 코딩테스트 031 - 내장함수의 시간 복잡도

문제31 : 자바스크립트 자료형의 복잡도

다음 배열 내장함수의 시간 복잡도가 O(1)이 아닌 것을 모두 고르시오.

1)  arr[i]
2)  arr.push(5)
3)  arr.slice()
4)  arr.pop()
5)  arr.includes(5)

정답) 3번

---

JavaScript의 내장 함수들은 대부분 최적화되어 있지만, 각 메서드마다 시간복잡도(Time Complexity) 가 다르다.

 

1. 배열(Array) 관련 메서드의 시간복잡도

메서드	설명	시간복잡도
push()	배열 끝에 요소 추가	O(1)
pop()	배열 끝 요소 제거	O(1)
unshift()	배열 앞에 요소 추가	O(n)
shift()	배열 앞 요소 제거	O(n)
indexOf()	특정 요소 찾기 (앞에서부터)	O(n)
lastIndexOf()	특정 요소 찾기 (뒤에서부터)	O(n)
includes()	특정 요소 존재 여부 확인	O(n)
find()	조건에 맞는 첫 번째 요소 찾기	O(n)
findIndex()	조건에 맞는 첫 번째 요소 인덱스 찾기	O(n)
findLastIndex()	조건에 맞는 마지막 요소 인덱스 찾기	O(n)
sort()	배열 정렬 (기본적으로 QuickSort 또는 Timsort)	O(n log n)
reverse()	배열 순서 뒤집기	O(n)
splice()	요소 추가/삭제	O(n)
slice()	배열 일부 복사	O(n)
concat()	배열 합치기	O(n)
map()	배열을 새 배열로 변환	O(n)
filter()	조건에 맞는 요소만 필터링	O(n)
reduce()	배열을 하나의 값으로 축소	O(n)

📌 push()와 pop()은 O(1)
하지만 unshift()와 shift()는 O(n) 이므로 앞쪽에서 요소 추가/삭제는 성능 저하가 발생할 수 있어요.

 

2. 문자열(String) 관련 메서드의 시간복잡도

메서드	설명	시간복잡도
indexOf()	특정 문자열 찾기	O(n)
lastIndexOf()	특정 문자열 찾기 (뒤에서부터)	O(n)
includes()	특정 문자열 포함 여부 확인	O(n)
charAt()	특정 위치 문자 반환	O(1)
substring()	문자열 일부 추출	O(n)
slice()	문자열 일부 추출	O(n)
split()	특정 구분자로 문자열 나누기	O(n)
replace()	문자열 치환 (첫 번째만)	O(n)
replaceAll()	문자열 치환 (전체)	O(n)
toUpperCase() / toLowerCase()	대소문자 변환	O(n)

 

3. 객체(Object) 관련 연산

연산	설명	시간복잡도
Object.keys()	키 목록 반환	O(n)
Object.values()	값 목록 반환	O(n)
Object.entries()	[key, value] 배열 반환	O(n)
hasOwnProperty()	특정 키 존재 여부 확인	O(1)

📌 객체에서 key in object 또는 hasOwnProperty() 는 해시 테이블을 사용하므로 O(1) 입니다.

 

4. Set과 Map의 시간복잡도
JavaScript의 Set과 Map은 내부적으로 해시 테이블(Hash Table) 을 사용하여, 대부분의 연산이 O(1) 입니다.

연산	Set	Map	시간복잡도
추가 (add() / set())	O(1)	O(1)
삭제 (delete())	O(1)	O(1)
검색 (has() / get())	O(1)	O(1)
크기 확인 (size)	O(1)	O(1)
순회 (forEach(), values(), keys())	O(n)	O(n)

📌 Set과 Map은 순서가 없는 데이터 저장에 최적화되어 있어서 배열보다 검색 속도가 빠릅니다.

 

---

정리

 

• 배열(Array)
  • push(), pop() → O(1)
  • unshift(), shift(), splice() → O(n)
  • indexOf(), find(), filter() → O(n)
  • sort() → O(n log n)
• 문자열(String)
  • charAt() → O(1)
  • replace(), split() → O(n)
• 객체(Object)
  • 키 조회, 값 조회 → O(n)
  • 키 존재 여부 (hasOwnProperty()) → O(1)
• Set / Map
  • 추가, 삭제, 검색 → O(1)
  • 순회 → O(n)

📌 Tip:

👉 빠른 검색이 필요하면 배열보다 Set이나 Map을 활용하는 것이 좋습니다!
👉 push()와 pop()을 활용하면 O(1)로 빠르게 데이터 추가/제거 가능!
👉 대량의 데이터를 다룰 때 시간복잡도를 고려하면 성능 최적화에 유리합니다.  

 

 

 

위 포스팅은 챗GPT 답변을 토대로 작성되었습니다!