[Daily morning study] Big-O 표기법: 시간 복잡도와 공간 복잡도
#daily morning study
Big-O 표기법: 시간 복잡도와 공간 복잡도
프로그래밍에서 알고리즘을 평가할 때, 그 성능을 정량적으로 비교하는 것이 중요하다. 그중 하나가 Big-O 표기법이다. 이 가이드는 시간 복잡도와 공간 복잡도의 개념을 설명하고, 각 개념의 이해를 돕기 위한 예제들을 포함한다.
1. Big-O 표기법의 정의
Big-O 표기법은 알고리즘의 실행 시간과 사용되는 메모리 양을 확실하게 설명하는 수학적 표기법이다. 데이터의 크기(n)가 증가함에 따라 알고리즘의 성능을 평가할 수 있도록 해준다. 이를 통해 최악의 경우 시간 복잡도나 공간 복잡도를 표기할 수 있다.
2. 시간 복잡도 (Time Complexity)
시간 복잡도는 알고리즘이 실행되는 데 소요되는 시간의 양을 데이터 입력 크기(n)에 따라 설명한다. 가장 많이 사용하는 시간 복잡도는 다음과 같다.
2.1. 상수 시간 복잡도 - O(1)
입력 크기와 관계없이 작업이 일정한 시간에 완료된다. 예를 들어, 배열의 특정 인덱스에 접근하는 경우.
def get_first_element(arr):
return arr[0]
2.2. 로그 시간 복잡도 - O(log n)
알고리즘이 입력 크기가 두 배가 될 때, 실행 시간이 일정한 비율로 증가한다. 이진 탐색을 예로 들 수 있다.
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
2.3. 선형 시간 복잡도 - O(n)
알고리즘의 실행 시간이 입력 크기와 직접 비례한다. 예를 들어, 배열의 모든 요소를 순회하는 경우다.
def print_elements(arr):
for element in arr:
print(element)
2.4. 선형 로그 시간 복잡도 - O(n log n)
많은 정렬 알고리즘, 예를 들어 병합 정렬이나 퀵 정렬의 복잡도이다. 입력 크기 n에 로그 시간 복잡도가 결합된다.
2.5. 제곱 시간 복잡도 - O(n^2)
중첩된 반복문을 가진 알고리즘으로, 입력 크기가 증가하면 실행 시간이 급격하게 증가한다. 예를 들어, 모든 쌍의 요소를 비교하는 경우이다.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
3. 공간 복잡도 (Space Complexity)
공간 복잡도는 알고리즘이 사용하는 메모리의 양을 설명하는 것이다. 시간 복잡도와 유사하게 입력 크기 n에 따라 설명된다.
3.1. 상수 공간 복잡도 - O(1)
알고리즘이 입력의 크기와 관계없이 일정한 양의 메모리를 사용하는 경우. 예를 들어, 단일 변수를 사용하는 경우다.
def add(a, b):
return a + b
3.2. 선형 공간 복잡도 - O(n)
입력 크기 n에 비례하여 메모리를 사용하는 경우다. 예를 들어, 입력 배열과 같은 크기의 새로운 배열을 생성하는 경우가 있다.
def create_copy(arr):
copy_arr = []
for element in arr:
copy_arr.append(element)
return copy_arr
4. 시간 복잡도와 공간 복잡도의 상관관계
시간 복잡도와 공간 복잡도는 종종 상반된 요구를 많이 가지게 된다. 메모리를 더 사용하는 알고리즘은 시간을 절약할 수 있는 경우가 많으며, 반대의 경우도 마찬가지다. 따라서 선택하는 알고리즘은 사용하는 환경이나 문제의 특성에 따라 다르게 결정될 수 있다.
5. 결론
Big-O 표기법은 알고리즘의 성능을 수학적으로 표현 할 수 있는 유용한 도구입니다. 시간 복잡도와 공간 복잡도를 이해함으로써, 더 효율적인 알고리즘을 선택하고 설계하는 데 도움이 될 것이다. 복잡도를 분석하는 습관을 기르고, 다양한 알고리즘을 실험함으로써, 이론과 실제의 차이를 줄이는 것이 중요하다.
