알고리즘 공부를 하며 시간 복잡도 계산에 대해 찾아보다,
많이 사용하는 빅오 계산법에 비해 빅오메가 계산법에 대한 정보는 별로 없어 이 글을 작성한다.
1. 시간 복잡도의 표현 방법
- 최상의 경우: Big-Ω Notation
- 평균의 경우: Big-θ Notation
- 최악의 경우: Big-O Notation
2. 시간 복잡도의 단계 (갈수록 비효율적)
O(1) < O(log N) < O(N) < O(N log N) < O (N²) < O (N³) < O( 2ⁿ ) < O(N!)
Big-Ω 경우는 역순이다.
3. 예제 풀이
sum = 0
for i in range(N):
for j in range(i):
sum += 1- 바깥쪽 i 반복문은 N번 반복된다.
- 안쪽 j 반복문은 i의 값에 따라 변동된다. 0부터 i - 1까지 반복된다.
- i = 0일 때 0번
- i = 1일 때 1번
- ...
- i = N - 1일 때 N - 1번
- 이 모든 반복을 더하면 등차수열의 합에 따라 N(N - 1) / 2 이다.
- 따라서 O(N²) 이다. ( Big-Ω의 경우도 동일하다. )
이번엔 Big-O와 Big-Ω의 값이 다르게 나오는 예제를 살펴보자.
선형탐색 예제
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
1. Big-O 계산법
최악의 경우는 배열의 모든 요소를 탐색한 후에 마지막에 target을 찾거나 찾지 못하는 경우이다.
arr = [3, 8, 5, 2, 9]다음과 같은 예시일 때, 탐색하려는 값이 9이거나 존재하지 않는다고 생각해보자. 총 5번 탐색하게 된다.
즉, 배열의 크기인 N번만큼 탐색하므로 시간 복잡도는 O(N)이다.
2. Big-Ω 계산법
최선의 경우는 탐색값이 3인 경우처럼 배열의 첫 번째 요소에서 바로 목표값을 찾는 경우이다.
이 경우 한 번의 비교만으로 탐색이 끝나기 때문에 시간 복잡도는 Ω (1), 즉 상수 시간이다.
이진탐색 예제
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
1. Big-O 계산법
최악의 경우는 배열의 모든 요소를 탐색한 후에 마지막에 target을 찾거나 찾지 못하는 경우이다.
이 경우 배열을 계속 절반으로 나누다가 마지막까지 탐색해야 한다.
매번 배열을 절반으로 나누기 때문에, 탐색 깊이는 로그 함수에 비례한다. 즉, 배열 크기가 N일 때 탐색 깊이는 O(log N)이다.
2. Big-Ω 계산법
최선의 경우는 배열의 첫 번째 요소에서 바로 목표값을 찾는 경우이다.
이 경우 한 번의 비교만으로 탐색이 끝나기 때문에 시간 복잡도는 Ω (1), 즉 상수 시간이다.
Big-O와 Big-Ω가 모두 낮은 경우를 택하면 좋겠지만, 이 둘은 반비례 관계라 이 경우가 성립하지 않는다.
둘 중에는 Big-O가 낮은 알고리즘을 택하는 것이 더 최선이다.
이는 최악의 경우에 대비하는 것이 더 현명한 선택이기 때문이라고 한다.