🔨[개발] 시간 복잡도와 공간 복잡도

1. 알고리즘이란?

• 알고리즘(Algorithm): 어떠한 목적을 이루기 위해 필요한 일련의 연산 절차.

• 알고리즘을 평가할 때 중요한 척도는 두 가지임.

  • 시간 복잡도(Time Complexity): 얼마나 오래 걸리는가?
  • 공간 복잡도(Space Complexity): 얼마나 메모리를 사용하는가?

---

2. 시간 복잡도 (Time Complexity)

2.1 정의

• 입력의 크기와 프로그램 실행 시간의 관계
• 실제 시간을 직접 측정하는 게 아니라, 연산 횟수 증가 추세를 기준으로 분석

2.2 가장 큰 영향을 주는 요소

• 반복문 (for, while 등)이 시간 복잡도를 결정하는 핵심 요소
• 중첩 루프가 늘어나면 복잡도도 기하급수적으로 증가

2.3 점근적 표기법

• 알고리즘의 성능을 나타낼 때는 보통 점근적 표기법(Asymptotic Notation)을 사용

점근적 표기법(Asymptotic Notation)

• 점근적 표기법은 알고리즘의 성능을 "입력 크기 n이 충분히 커질 때"의 실행 시간 증가 추세로 표현하는 방법
• 즉, 작은 n에서는 하드웨어나 상수 차이가 영향을 줄 수 있지만, 큰 n에서의 성장률이 알고리즘의 진짜 성능을 보여준다고 보는 것
• 가장 큰 항(N²)만 남겨서 단순화 O(N² + 3N + 5) → O(N²)
  → 알고리즘의 효율성을 수학적으로 단순화해서 표현하는 도구

1. Big-O (O)

   • 최악의 경우(Worst Case)를 나타냄
   • 알고리즘 실행 시간의 상한선

2. Big-Theta (Θ)

   • 평균적인 경우(Average Case)를 나타냄
   • 알고리즘 실행 시간의 정확한 증가율

3. Big-Omega (Ω)

   • 최선의 경우(Best Case)를 나타냄
   • 알고리즘 실행 시간의 하한선

2.4 자주 보이는 시간 복잡도

• O(1): 상수 시간 (예: 배열 인덱스 접근 → RAM을 생각하라!)
• O(log n): 로그 시간 (예: 이진 탐색, 밑이 2진수다!)
• O(n): 선형 시간 (예: 배열 전체 탐색)
• O(n log n): 로그 선형 시간 (예: 효율적인 정렬 알고리즘)
• O(n²): 이차 시간 (예: 버블 정렬)
• O(2ⁿ): 지수 시간 (예: 부분집합 생성)
• O(n!): 팩토리얼 시간 (예: 외판원 순회 문제 Brute-Force)
  

2.5 정렬 알고리즘 시간 복잡도

알고리즘	평균	최악	최선
버블 정렬	O(n²)	O(n²)	O(n)
선택 정렬	O(n²)	O(n²)	O(n²)
삽입 정렬	O(n²)	O(n²)	O(n)
병합 정렬	O(n log n)	O(n log n)	O(n log n)
퀵 정렬	O(n log n)	O(n²)	O(n log n)
힙 정렬	O(n log n)	O(n log n)	O(n log n)

---

3. 공간 복잡도 (Space Complexity)

3.1 정의

• 입력 크기와 메모리 공간의 관계.
• 단순히 코드 크기뿐만 아니라, 변수, 함수 호출 스택, 동적 메모리 할당 등을 모두 포함
• 오늘날 알고리즘의 성능 판단에 사용되는 척도는 주로 공간 복잡도보다는 시간 복잡도인 경우가 많음

3.2 구성 요소

1. 고정 공간: 프로그램 코드, 상수, 컴파일 시 할당되는 공간 (입력 크기와 무관)
2. 가변 공간: 입력 크기에 따라 달라지는 공간 (배열, 동적 구조, 재귀 스택 등)

3.3 예시

• 배열에 n개의 데이터를 저장 → O(n)
• 재귀 알고리즘 호출 깊이가 n → O(n) 스택 공간 필요