📌 소프트웨어 복잡도 개념 정리 🚀
소프트웨어 복잡도는 알고리즘이나 프로그램의 복잡성을 평가하고 최적화하는 기준입니다.
복잡도가 높으면 코드 실행 속도가 느려지고, 유지보수가 어려워질 수 있습니다.
1️⃣ 복잡도(Complexity)란?
📌 소프트웨어 복잡도의 정의
- 시스템 또는 소프트웨어의 구조와 동작이 얼마나 복잡한지 나타내는 정도
- 복잡도가 높을수록 테스트 난이도 상승, 성능 저하, 유지보수 어려움 발생
📌 복잡도 분석이 중요한 이유?
✔ 최적의 알고리즘 선택 (성능 개선)
✔ 리소스 낭비 방지 (CPU, 메모리 효율성 증대)
✔ 소프트웨어 유지보수 용이성 향상
2️⃣ 시간 복잡도(Time Complexity)
📌 시간 복잡도란?
- 알고리즘이 수행되는 연산 횟수를 수치화한 것
- 입력 크기(n)에 따라 연산 횟수가 얼마나 증가하는지 측정
- 실행 시간(Time)이 아니라 연산 횟수(Operations)를 기준으로 판단
📌 시간 복잡도의 핵심 개념
✔ 시간 복잡도가 낮을수록 성능이 좋은 알고리즘
✔ 연산 횟수가 적으면 실행 속도가 빠름
✔ 입력 크기(n)에 따른 연산 횟수 증가 패턴이 중요
3️⃣ 시간 복잡도 표기법 (Big-O Notation)
📌 알고리즘의 성능을 분석할 때 사용하는 표기법
- 가장 많이 사용하는 것은 Big-O 표기법 (O 표기법)
- 알고리즘이 최악의 경우(최대 연산 횟수) 를 기준으로 평가
- 입력 크기(n)가 커질 때 알고리즘의 실행 시간이 어떻게 증가하는지 분석
📌 시간 복잡도 종류 및 예시
| Big-O 표기법 | 의미 | 예시 |
|---------------|--------|-------|
| O(1) | 상수 시간 (입력 크기와 관계없이 일정한 실행 시간) | 배열 인덱스 접근 |
| O(log n) | 로그 시간 (입력이 증가할수록 연산 횟수는 서서히 증가) | 이진 탐색(Binary Search) |
| O(n) | 선형 시간 (입력 크기만큼 실행) | 단순 반복문(For Loop) |
| O(n log n) | 로그 선형 시간 | 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort) |
| O(n²) | 이차 시간 (입력이 증가할수록 연산 횟수가 제곱 증가) | 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort) |
| O(2ⁿ) | 지수 시간 (입력이 조금만 증가해도 연산 횟수가 급증) | 피보나치 재귀 (Fibonacci) |
| O(n!) | 팩토리얼 시간 (가장 느린 알고리즘) | 외판원 문제 (TSP) |
📌 💡 예제:
✔ O(1): 배열에서 특정 원소 접근 → arr[0]
✔ O(n): 배열 전체 탐색 → for i in range(n):
✔ O(log n): 이진 탐색 → Binary Search
✔ O(n²): 버블 정렬 → for i in range(n): for j in range(n):
4️⃣ 시간 복잡도 표기법 종류
📌 Big-O 표기법 이외에도 2가지 표기법이 더 있음
| 표기법 | 설명 |
|---|---|
| Big-O (O) | 최악의 경우 시간 복잡도 |
| 세타(Θ, Theta) | 평균적인 시간 복잡도 |
| 오메가(Ω, Omega) | 최상의 경우 시간 복잡도 |
📌 예제: 정렬 알고리즘
✔ 버블 정렬 (Bubble Sort)
- O(n²) (최악, Big-O)
- Θ(n²) (평균, Theta)
- Ω(n) (최상, Omega)
✔ 퀵 정렬 (Quick Sort)
- O(n²) (최악, Big-O)
- Θ(n log n) (평균, Theta)
- Ω(n log n) (최상, Omega)
5️⃣ 공간 복잡도(Space Complexity)
📌 공간 복잡도란?
- 알고리즘이 실행될 때 추가로 필요한 메모리 공간
- 코드, 변수, 자료구조, 함수 호출 등이 차지하는 공간 포함
📌 공간 복잡도 표기법
| Big-O 표기법 | 설명 | 예시 |
|--------------|--------|------|
| O(1) | 추가 공간을 거의 사용하지 않음 | 변수 1~2개 사용 |
| O(n) | 입력 크기만큼 추가 공간 사용 | 배열 할당 arr[n] |
| O(n²) | 2차원 배열 사용 | matrix[n][n] |
📌 💡 예제:
✔ O(1): 정수형 변수 1~2개 사용
✔ O(n): 배열에 n개의 원소 저장
✔ O(n²): n x n 크기의 행렬
6️⃣ 순환 복잡도 (Cyclomatic Complexity)
📌 순환 복잡도란?
- 프로그램의 논리적 복잡도를 측정하는 척도
- 코드의 제어 흐름(Flow)을 분석하여 테스트 난이도를 예측
- 복잡도가 높으면 디버깅 및 유지보수 어려움
📌 계산 방법 (McCabe’s Cyclomatic Complexity)
✔ 방법 1: 제어 흐름 다이어그램에서 영역(Regions) 개수
✔ 방법 2: V(G) = E - N + 2 (E=Edges, N=Nodes)
📌 💡 예제: 순환 복잡도 계산
✔ 단순한 If-Else 문: 복잡도 낮음 (V(G) = 2~3)
✔ 중첩된 반복문 (Nested Loops): 복잡도 증가 (V(G) > 10)
✅ 결론 및 정리
✔ 소프트웨어 복잡도는 시스템의 복잡한 정도를 수치화한 것
✔ 시간 복잡도는 연산 횟수를 측정하는 기준 (O 표기법 중요!)
✔ 공간 복잡도는 알고리즘 실행에 필요한 메모리 공간
✔ 순환 복잡도는 코드의 제어 흐름 분석하여 복잡도 측정
✔ Big-O, Theta, Omega 표기법 차이점 이해 필수!
✅ 이제 소프트웨어 복잡도 개념이 확실해졌나요? 🚀
시험 대비 및 실무 활용을 위해 개념을 정확히 숙지하세요! 💯
