순서복잡도 (Time Complexity)

순서복잡도가 뭐고, 왜 중요한가? 

 

뭔지

 순서 복잡도는 알고리즘이나 코드가 실행되는 시간이나 연산 횟수를 데이터 크기(n)에 따라 수학적으로 표현한 것이다. 예를 들어, O(1)은 데이터 크기와 상관없이 항상 일정한 시간이 걸리고, O(n)은 데이터가 커질 수록 비례해서 시간이 늘어나는 것이다. 

 

=> 코드가 얼마나 빨리 끝나느냐를 데이터 크기에 따라 숫자로 나타낸 것

 

왜 중요한지 

 시간과 돈이 걸려있다. 

 

1. 서비스 성능 : 사용자가 10명일 땐 O(n)을 써도 괜찮다. 100만 명이 되면 서버가 터질 수도 있다. 예를 들어, 책 목록 검색을 List로 하면 느려지는데 Set으로 바꾸면 빠르게 응답 가능하다. 

 

2. 확장성: 처음엔 데이터 적어서 문제없었던 게 나중에 커지면 망가질 수 있다. 순서복잡도 보면 미리 대비할 수 있다. (ex: List로 중복 체크하다가 데이터 늘어나 속도 저하되니 Set으로 바꾸기)

 

3. 효율적 설계: O(1)이 항상 조은 건 아니다. 단순 조회만 하면 ArrayList가 더 나을 수도 있따. 상황에 맞게 골라야 한다. 

 

 

 

 List에서 특정한 값을 찾으려면 contains()를 써서 순차 탐색하면 O(n)이 걸리는데, 데이터가 100만 개면 최악의 경우 100만 번 확인해야 한다. 반면 Set, 특히 HashSet은 O(1)이라 거의 즉시 찾을 수 있다. 이 차이는 서비스가 느려지느냐 빠르냐를 결정할 수 있다. 

 

---

EXAMPLE

EX: List vs Set으로 값 찾기

List 탐색:
[ "Book A" → "Book B" → ... → "Book Z" ] (100만 번 화살표)

Set 탐색:
[ "Book Z" ] → (해시 계산) → [ 찾음! ] (한 번 화살표)

상황

• 데이터: 100만 개 (n = 1,000,000).
• 찾으려는 값: "Book Z" (최악의 경우, 리스트 끝에 있거나 없는 경우 가정).
• List: ArrayList<String> → 순차 탐색.
• Set: HashSet<String> → 해시 기반 탐색.

1. List에서 contains()로 찾기: O(n)

동작

• ArrayList는 배열 기반이라 값을 찾으려면 처음부터 끝까지 하나씩 확인.
• list.contains("Book Z") → 인덱스 0부터 999,999까지 순차적으로 비교.

시각화

ArrayList: [ "Book A", "Book B", "Book C", ..., "Book Y", "Book Z" ]
             ↑         ↑         ↑               ↑         ↑
            [0]       [1]       [2]            [999,998] [999,999]
탐색 경로:  → → → → → → → → → → → → → → → → → → → → → → → → (최대 100만 번)

• 최악의 경우: "Book Z"가 맨 끝에 있거나 없으면 100만 번 확인.
• 시간: O(n) → 데이터 크기에 비례. 100만 개면 최대 100만 번 연산.

비유

• 책상 위에 책 100만 권 쌓여있고, "Book Z" 찾으려면 한 권씩 뒤져야 함.
• 최악으론 100만 권 다 뒤져야 끝남 → 시간 오래 걸림.

---

2. Set에서 contains()로 찾기: O(1)

동작

• HashSet은 해시 테이블 기반이라 "Book Z"의 해시값을 계산해 바로 위치로 감.
• set.contains("Book Z") → 해시 함수로 버킷 찾아 즉시 확인.

시각화

HashSet 내부 (해시 테이블):
  버킷: [0]   [1]   [2]   ...   [k]         ...   [m]
        "Book A" "Book B"       "Book Z"          "Book Y"
탐색 경로: "Book Z" → hash("Book Z") = k → 바로 [k] 확인

• 과정:
  
  1. "Book Z"의 해시값 계산 (예: k).
  2. 버킷 k로 바로 이동.
  3. equals()로 확인 후 끝.
• 최악의 경우: 충돌이 있으면 약간 더 걸리지만, 평균 O(1).
• 시간: 데이터 100만 개든 10억 개든 거의 일정 (충돌 제외).

비유

• 책 100만 권이 책장에 인덱스 카드처럼 정리돼 있고, "Book Z"가 어디 있는지 색인표로 바로 찾아감.
• 한 번에 딱 찾음 → 거의 즉시 끝.

---

3. TreeSet에서 contains()로 찾기: O(log n)

동작

• 정렬된 이진 탐색 트리 (Red-Black Tree) 기반
• 데이터가 정렬되어 있어 비교하며 절반씩 범위 줄임

시각화

TreeSet (이진 탐색 트리):
          "Book M"          ← 루트
         /        \
    "Book F"    "Book T"
    /     \         /    \
 "Book B" "Book J" "Book R" "Book Z"
탐색 경로:
1. "Book Z" > "Book M" → 오른쪽
2. "Book Z" > "Book T" → 오른쪽
3. "Book Z" = "Book Z" → 찾음!

 

과정:

1. 100만 개면 트리 높이 ≈ log₂(1,000,000) ≈ 20.
2. 매번 절반씩 줄여서 최대 20만 번 비교.

• 최악의 경우: 평균 O(log n) --> 100만 개면 약 20번 연산
• 비유: 책 100만 권이 사전처럼 정렬돼 있고, 중간 페이지를 펼쳐가며 절반씩 좁혀감.

결과

• 20번 연산  ≈ 수십 밀리초 (정확히는 환경 의존).

데이터 개수 (n)	List 탐색 (O(n))	Set 탐색 (O(1))	TreeSet (O(log n))
10	10번 확인	1번 확인	~3번 (log₂10 ≈ 3.3)
1,000	1,000번 확인	1번 확인	~10번 (log₂1,000 ≈ 10)
1,000,000	1,000,000번 확인	1번 확ㅇ니	~20번 (log₂1M ≈ 20)

 

시간
↑
|       ArrayList (O(n)) → 급격히 올라감
|      /
|     /
|    / TreeSet (O(log n)) → 완만히 증가
|   /|
|  / |
|_/___ HashSet (O(1)) → 평평
+----------------→ 데이터 크기 (n)

 

 - O(n) : 직선으로 쭉 올라감 --> 데이터 많아질 수록 부담 커짐

 - O(log n): 로그 곡선 --> 느리게 증가, 큰 데이터에서도 괜찮음

 - O(1) 수평선 --> 언제나 빠름

---

List: 느려질 수 있음

[ 검색 중... ] → [ 검색 중... ] → [ 결과 ]
(100만 번 ≈ 수 초 로딩)

• 100만 개 데이터에서 O(n) → 100만 번 연산 ≈ 수 초 걸릴 수 있음.
• 사용자가 책 검색 버튼 누르면 로딩바 돌다가 "왜 이렇게 느려?" 불만.

Set: 빠름

[ 검색 ] → [ 결과 ]
(1번 ≈ 밀리초 내)

or

[ 검색 중 ] → [ 결과 ]
(20번 ≈ 수십 밀리초)

• 100만 개 데이터에서 O(1) → 1번 연산 ≈ 밀리초 내 끝.
• 검색 버튼 누르자마자 결과 뿅! → "오, 빠르네!"

 

---

각 자료구조의 장단점

• ArrayList (O(n)):
  
  • 장점: 순서 유지, 중복 허용, 삽입 빠름.
  • 단점: 검색 느림.
• HashSet (O(1)):
  
  • 장점: 검색/추가/삭제 빠름, 중복 제거.
  • 단점: 순서 없음, 메모리 조금 더 씀.
• TreeSet (O(log n)):
  
  • 장점: 정렬 유지, 검색/추가/삭제 적당히 빠름.
  • 단점: 삽입/삭제 시 트리 균형 맞추느라 O(log n).

 

 

---

그렇다면 O(1)이 언제나 개꿀이냐? 

O(1)은 시간복잡도 면에서 개꿀이지만, 자료구조마다 트레이드 오프가 있어서 상황에 따라 다른 선택이 필요하다. O(1)은 항상 최고가 아니다.

 

1. 기능의 한계: O(1)으로 모든 걸 해결할 수 없다. 

HashSet O(1):
     - 검색, 추가, 삭제는 O(1)로 빠르다.

     - 그러나 순서 보장이 안된다. 넣은 순서대로 보고 싶으면? 오 ㅂㅂ

     - 또 중복 제거는 되지만, 중복을 허용해야하는 경우엔 못 쓴다.

 

ex: 책 목록을 순서대로 보여줘야 한다면 HashSet은 엉망이다. [Book A, Book Z, Book B] 이렇게 나올 수 있다.

 

ArrayList O(n) : 
     - 순서 유지하고 중복도 ㄱㅊ

     - 검색은 느려도 인덱스 접근(O(1))이나 순차 출력은 빠르다. 

 

ex: 주문 내역 [Order1, Order2, Order3] 처럼 중복 허용하고 순서 필요한 경우 HashSet은 안 맞다. 

 

 

 

2. 숨은 비용: O(1)은 공짜가 아니다.

HashSet:
     - 해시 테이블 쓰니까 메모리를 더 먹는다. (버킷 관리)

     - 해시 충돌 (Hash Collision)이 생기면 O(1)이 아니라 O(n)에 가까워질 수도 (드물지만)

     - 해시값 개산(hashCode()) 자체도 약간의 비용이 있다. 

 

ex: "Book Z" 찾을 때 색인으로 바로 찾는 건 빠르지만, 색인표 만드는 데 처음에 시간과 공간이 든다.

 

TreeSet (O(log n)):
     - 정렬된 상태 유지 --> 메모리와 연산 더 쓰지만, 검색뿐 아니라 "정렬된 결과"도 준다.

 

ArrayList:
     - 메모리 효율 좋고 단순 배열이라 초기 비용이 적다.

 

 

3. 요구사항 문제: O(1)이 필요없는 경우도 많다.

 

데이터가 작으면(예: 10개), O(n)이든 O(1)이든 체감 차이가 없다;;

     - List.contains() : 10번 = 밀리초 미만.

     - Set.contains() : 1번 = 거의 비슷 

 

순서나 중복이 더 중요하면 O(1) 속도보다 그 기능 우선.

 

---

∴ 

뭐가 제일 좋다 가 아니라 상황에 맞는 걸 골라야 한다