알고리즘의 성능 분석
알고리즘의 성능을 분석하는 주요 지표로 시간 복잡도와 공간 복잡도가 있다.
- 시간 복잡도: 문제를 푸는 데 걸리는 시간
- 공간 복잡도: 문제를 푸는 데 사용되는 메모리 사용량
시간 복잡도를 계산할 때는 연산의 실행 횟수를 계산하며, 계수를 제거하고 가장 차수가 높은 항만 남긴다. 공간 복잡도는 프로그램 실행에 필요한 저장 공간을 분석한다.
빅오 표기법(Big-O Notation)
빅오 표기법은 알고리즘의 수학적 성능을 표기하는 방식으로, 시간과 공간 복잡도를 표현할 수 있다. 이는 단순히 알고리즘의 성능을 측정하는 것이 아니라, 데이터 증가율에 따라 알고리즘 성능을 예측하는 데 사용된다.
공간 복잡도보다 주요적인 시간 복잡도를 중점으로 포스트하였다.
주요 시간 복잡도 분석
O(1) 알고리즘 (Constant Time)
입력 데이터의 크기에 상관없이 일정한 시간이 걸리는 알고리즘.
def example(n): # n은 리스트 혹은 배열
return True if n[0] == 0 else False
위 코드에서는 0번째 인덱스의 값이 0인지 확인하는 연산만 수행하므로 입력 크기에 관계없이 일정한 실행 시간을 가진다.
O(1) 알고리즘 (Constant Time) 그래프
O(n) 알고리즘 (Linear Time)
입력 값이 증가할 때마다 처리 시간이 선형적으로 증가하는 알고리즘.
def example(n): # n은 리스트 혹은 배열
for i in range(len(n)):
print(i)
입력 크기가 n일 때, n번 루프를 돌며 실행되므로 O(n)의 시간 복잡도를 가진다.
O(n) 알고리즘 (Linear Time) 그래프
O(n log n) 알고리즘 (Quasilinear Time)
정렬 알고리즘(예: 병합 정렬, 힙 정렬 등)이 대표적인 예시이며, 데이터가 증가할수록 로그 비율로 증가하는 시간 복잡도를 가진다.
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)
def merge(left, right):
result = []
while left and right:
if left[0] < right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
return result + left + right
위 병합 정렬 알고리즘의 시간 복잡도는 O(n log n)이다.
O(n²) 알고리즘 (Quadratic Time)
입력 크기에 대해 제곱 비율로 연산이 증가하는 알고리즘.
def example(n): # n은 리스트 혹은 배열
for i in range(n):
for j in range(n):
print(i + j)
이중 루프를 사용하여 n × n번의 연산을 수행하므로 시간 복잡도는 O(n²)이다.
O(n²) 알고리즘 (Quasilinear Time) 그래프
O(n³) 알고리즘 (Cubic Time)
입력 크기에 대해 세제곱 비율로 연산이 증가하는 알고리즘.
def example(n): # n은 리스트 혹은 배열
for i in range(n):
for j in range(n):
for k in range(n):
print(i + j + k)
삼중 루프를 사용하여 n³번의 연산을 수행하므로 시간 복잡도는 O(n³)이다.
O(2ⁿ) 알고리즘 (Exponential Time) - 피보나치 수열
재귀 호출을 사용하여 피보나치 수열을 계산하는 알고리즘은 O(2ⁿ)의 시간 복잡도를 가진다.
def fibonacci(n):
if n <= 0:
return 0
elif n == 1:
return 1
return fibonacci(n - 1) + fibonacci(n - 2)
이 알고리즘은 동일한 연산을 여러 번 반복하게 되므로 O(2ⁿ)의 시간 복잡도를 가진다.
O(log n) 알고리즘 (Logarithmic Time) - 이진 검색
이진 검색과 같은 알고리즘은 처리할 데이터의 수가 반복될 때마다 절반으로 줄어들며, O(log n)의 시간 복잡도를 갖는다.
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
O(√n) 알고리즘 (Square Root Time)
일부 특정 알고리즘에서 발생하는 시간 복잡도로, 데이터 크기의 제곱근만큼 실행되는 알고리즘이다.
빅오 표기법에서 상수 제거
빅오 표기법에서는 상수를 무시한다. 예를 들어:
def example(n): # n은 정수 배열, 리스트
for i in range(len(n)):
print(i)
for i in range(len(n)):
print(i)
위 코드의 시간 복잡도는 O(2n)이 아니라 O(n)으로 표기된다. 이는 데이터가 증가할수록 일정한 상수는 무시할 수 있기 때문이다.
def example(n): # n은 정수 배열, 리스트
for i in range(len(n)):
for j in range(len(n)):
print(i + j)
for i in range(len(n)):
for j in range(len(n)):
print(i + j)
이 경우 O(n² + n²)으로 보일 수 있지만, 빅오 표기법에서는 O(n²)으로 단순화하여 표기한다. 이는 데이터가 증가할 때 지배적인 차수만 고려하기 때문이다.
