계산량(오더 표기, Big-O Notation): 알고리즘 성능 분석의 핵심 개념
🔹 계산량이란?
1. 계산량(Computational Complexity)의 정의
계산량(Computational Complexity)이란 알고리즘이 실행되는 동안 필요한 연산의 양을 측정하는 개념으로, 주어진 입력 크기에 대해 알고리즘이 얼마나 빠르게 실행되는지를 분석하는 데 사용됩니다.
✅ 계산량 분석의 주요 요소:
- 시간 복잡도(Time Complexity): 알고리즘이 실행되기까지 걸리는 연산 횟수
- 공간 복잡도(Space Complexity): 알고리즘이 실행되는 동안 사용하는 메모리 양
- 최선, 평균, 최악의 경우 분석
- 입력 크기(n)에 따라 성능이 어떻게 변화하는지 분석
📌 계산량 분석은 알고리즘 성능 최적화와 효율적인 프로그램 개발을 위한 필수 과정입니다.
🔹 오더 표기(Big-O Notation)란?
1. 오더 표기(Big-O Notation)의 개념
오더 표기(Big-O Notation)는 입력 크기(n)에 대한 시간 또는 공간 복잡도의 증가율을 수학적으로 표현하는 방법입니다. 주어진 알고리즘이 입력 크기에 따라 얼마나 효율적인지를 비교할 때 사용됩니다.
✔️ 오더 표기의 주요 특징:
- 최악의 경우(Worst Case) 성능을 기준으로 표현
- 입력 크기가 매우 클 때(Asymptotic) 성능을 측정
- 상수 및 낮은 차수의 항은 무시하고 주요 차수만 표기
📌 Big-O 표기는 알고리즘의 성능을 직관적으로 비교할 수 있도록 도와줍니다.
🔹 대표적인 시간 복잡도(Big-O) 분류
1. O(1) - 상수 시간(Constant Time)
✅ 입력 크기(n)와 관계없이 항상 일정한 시간이 걸리는 알고리즘
✔️ 예제:
def constant_time(arr):
return arr[0] # 첫 번째 요소 반환 (항상 O(1))📌 해시 테이블 조회, 배열의 특정 인덱스 접근 등이 O(1) 시간 복잡도를 가집니다.
2. O(log n) - 로그 시간(Logarithmic Time)
✅ 입력 크기가 증가할수록 실행 시간이 느리게 증가하는 알고리즘
✔️ 예제:
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1📌 이진 탐색(Binary Search)과 같은 알고리즘이 O(log n) 복잡도를 가집니다.
3. O(n) - 선형 시간(Linear Time)
✅ 입력 크기에 비례하여 실행 시간이 증가하는 알고리즘
✔️ 예제:
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1📌 리스트 탐색(순차 검색)과 같은 알고리즘이 O(n) 복잡도를 가집니다.
4. O(n log n) - 선형 로그 시간(Linearithmic Time)
✅ 입력 크기가 증가할수록 실행 시간이 n log n 비율로 증가하는 알고리즘
✔️ 예제:
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)📌 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort)과 같은 정렬 알고리즘이 O(n log n) 복잡도를 가집니다.
5. O(n²) - 이차 시간(Quadratic Time)
✅ 입력 크기의 제곱에 비례하여 실행 시간이 증가하는 알고리즘
✔️ 예제:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]📌 버블 정렬(Bubble Sort), 선택 정렬(Selection Sort) 등이 O(n²) 복잡도를 가집니다.
6. O(2ⁿ) - 지수 시간(Exponential Time)
✅ 입력 크기가 증가할수록 실행 시간이 급격히 증가하는 알고리즘
✔️ 예제:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)📌 재귀적 피보나치(Fibonacci) 알고리즘이 O(2ⁿ) 복잡도를 가집니다.
7. O(n!) - 계승 시간(Factorial Time)
✅ 입력 크기가 증가할수록 실행 시간이 극단적으로 증가하는 알고리즘
✔️ 예제:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)📌 외판원 문제(Travelling Salesman Problem, TSP)와 같은 최적화 문제에서 O(n!) 복잡도가 나타납니다.
📌 결론
✅ 오더 표기(Big-O Notation)는 알고리즘의 실행 속도를 분석하는 핵심 개념입니다.
✅ O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ) → O(n!) 순으로 성능이 감소합니다.
✅ 알고리즘의 시간 복잡도를 최적화하면 실행 속도와 성능을 향상할 수 있습니다.
✅ 효율적인 알고리즘을 선택하고, 필요에 따라 최적화를 수행해야 합니다.