구름톤 챌린지 4주차 학습 일기 v2 - Set과 Array의 시간복잡도 비교

 

궁금한 점

---

알고리즘을 풀 때, 특정 값을 찾기 위해서 배열을 주로 사용하는데, 시간복잡도가 최악의 경우 배열의 길이만큼 걸릴 수 있기 때문에 비효율적이라는 생각이 들었다.

그래서 이걸 Set으로 관리하면 시간 복잡도가 줄어들지 않을까?라는 생각이 들었고, 내 생각이 맞는지 알아보기 위해 정리하게 되었다. 

 

 

Set

---

• Set은 중복되지 않는 값을 저장하는 자료구조이다. 
• Set은 내부적으로 해시 테이블과 같은 자료구조를 사용해서 값을 저장한다. 
• 값을 찾을 때 O(1)의 시간복잡도로 검색할 수 있다.

 

Array

---

• 순서대로 값을 저장하는 자료구조이다. 
• 중복 여부에 대한 제약은 없다. 
• 배열의 각 요소를 순회하며 값을 찾아야 하기 때문에, 최악의 경우 배열의 길이에 비례하는 O(n)이 소요된다. 

 

 

결론

---

정리하자면, Set은 값의 존재 여부를 빠르게 파악할 수 있고, 해시 테이블을 사용해서 중복을 허용하지 않고 데이터를 저장한다. 

하지만 배열은 배열의 길이가 커질수록 그 길이만큼 검색 시간이 증가하기 때문에 Set보다 더 많은 시간 복잡도가 소요된다. 

 

결론적으로 내 생각이 맞았다!