📌 시간 복잡도란?

✅ 어떤 코드(알고리즘)가 데이터 크기(N) 에 따라 얼마나 빨리(또는 느리게) 실행되는지를 수학적으로 표현한 것

• 여기서 O(...) 는 "Order of" 라는 뜻이고, 대략적인 실행 시간의 크기(성장률) 를 말한다.

📌 자주 나오는 시간 복잡도들

1. O(1) → 상수 시간(Constant Time)

• 데이터 개수(N)와 상관없이 실행 시간이 항상 일정한 경우
• 예: 배열에서 인덱스로 값 꺼내오기 (arr[5])

👉 데이터가 10개든, 100만 개든, "한 번에" 가져옴

2. O(n) → 선형 시간(Linear Time)

• 데이터 개수(N)에 비례해서 시간이 걸리는 경우
• 예: 배열에서 특정 값 찾기 (하나하나 다 확인해야 함)

👉 데이터가 10개면 10번, 100만 개면 100만 번

3. O(n²) → 제곱 시간(Quadratic Time)

• 이중 반복문 같은 경우
• 예: 모든 학생을 비교해서 짝을 찾는 알고리즘

👉 데이터가 많아질수록 기하급수적으로 느려짐

📌 직관적인 예시 (사람 이름 찾기)

• O(1) : 전화번호부에서 특정 페이지 번호 바로 열기
  → "5쪽 주세요" 하면 바로 펴줌 (데이터 크기 상관 없음)

• O(n) : 전화번호부 처음부터 끝까지 이름 찾기
  → 이름이 뒤에 있으면 다 뒤져야 함 (데이터 많아질수록 시간 ↑)

• O(n²) : 모든 사람을 서로 짝 지어 대화 시키기
  → 학생이 100명이면 100×100 = 10,000번 짝 맞추기