복잡도란
복잡도(Complexity)란 알고리즘의 성능을 나타내는 척도이며, 일반적으로 시간 복잡도와 공간 복잡도로 나뉜다.
- 시간 복잡도 : 알고리즘의 실행 시간, 즉 연산 수행 횟수를 측정하는 척도이다.
- 공간 복잡도 : 알고리즘이 실행되는 동안 필요한 메모리의 양을 측정하는 척도이다.
효율적인 알고리즘을 사용한다고 했을 때, 시간 복잡도와 공간 복잡도는 서로 상반된 관계를 형성할 수 있다. 즉, 빠른 알고리즘은 종종 더 많은 메모리 공간을 필요로 하며, 반대로 공간 효율적인 알고리즘은 더 많은 시간이 소요될 수 있다.
수식어 없이 '복잡도'라고 할 경우, 두 가지 중 일반적으로 시간 복잡도를 의미한다. 알고리즘 문제를 해결할 때 가장 흔히 직면하는 문제는 '시간 초과'이며, 문제의 특성에 따라 다르지만, 보통 500ms에서 2000ms 정도의 제한된 시간 내에 알고리즘이 올바른 형식으로 값을 출력해야 한다.
시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용하며, 이는 알고리즘의 "최악의 실행 시간"을 나타낸다. 즉, 알고리즘의 성능을 평가할 때, 가장 빠르게 증가하는 항만을 고려하여 작성된 표기법이다. 이 표기법은 알고리즘의 성능과 효율성을 비교하는 데 중요한 기준이 된다.
빅오 표기법
빅오(Big-O) 표기법은 알고리즘의 시간 복잡도를 표현할 때 가장 널리 사용되는 표기법으로, 알고리즘의 성능을 최악의 경우를 기준으로 나타낸다. 빅오 표기법은 알고리즘의 입력 크기(n)가 증가함에 따라 실행 시간이 어떻게 변화하는지를 설명하며, 최악의 실행 시간을 기준으로 성능을 평가한다.
아래의 간단한 파이썬 예시 코드를 통해 알고리즘의 시간 복잡도를 쉽게 이해할 수 있다.
O(n) 예시 코드
data = [5,2,1,3,4]
for elem in data:
print(elem)
위의 코드는 배열(data)의 모든 원소(elem)에 각 한 번씩 접근해 출력하고 있다. 원소의 개수를 5개에서 10개로 늘린다면, 모든 원소를 한 번씩 출력하기 위해 반복 횟수도 10번으로 늘어날 것이다. 원소의 개수가 N개라면, 반복 횟수도 N회가 된다.
배열(입력)의 크기 증가에 따라 실행 시간도 선형적으로 증가했으므로, 이는 "선형 증가"에 해당하는 알고리즘이다. 빅오 표기법은 입력 크기 N에 비례하는 시간 복잡도라는 의미에서 이 알고리즘의 시간 복잡도를 O(N)으로 표기한다.
O(1) 예시 코드
data = [5,2,1,3,4]
idx = 3
print(data[idx])
위의 코드는 배열(data)에서 특정 인덱스(idx)의 값에 접근하는 연산을 다룬다. 원소의 개수를 5개에서 24,000개로 늘린다 하더라도, 특정 인덱스의 값을 접근하는 연산에 필요한 시간은 변하지 않는다.
배열(입력)의 크기 증감과 상관 없이 연산에 항상 일정한 시간이 소요되므로, 시간 복잡도는 O(1)이다.
빅오 표기법과 명칭
| 빅오 표기법 | 명칭 |
| O(1) | 상수 시간 |
| O(log N) | 로그 시간 |
| O(N) | 선형 시간 |
| O(N log N) | 로그 선형 시간 |
| O(N^2) | 이차 시간 |
| O(N^3) | 삼차 시간 |
| O(2^n) | 지수 시간 |
로그(log) 복잡도에 대한 이해
로그 시간 복잡도는 주로 이진 탐색에서 나타난다. 이 알고리즘은 입력 데이터가 정렬되어 있을 때 유효하며, 입력 크기 N에 대해 로그 함수 형태로 증가한다. 즉, 입력 크기가 두 배로 늘어날 때 알고리즘의 실행 시간이 한 단계만 증가한다는 의미이다.
아래의 이진 탐색(Binary search) 코드는 대표적인 로그 시간 알고리즘이다.
# 이진 탐색
def bisect(data, value):
low, high = 0, len(data) - 1
while low <= high:
mid = (low + high) // 2 # 가운데 인덱스 계산
if data[mid] == value:
return mid
elif data[mid] < value:
low = mid + 1 # 목표값이 중간값보다 크면 오른쪽 탐색
else:
high = mid - 1 # 목표값이 중간값보다 작으면 왼쪽 탐색
return -1 # 찾지 못함
data = [1, 3, 5, 7, 9, 11, 13, 15] # 기정렬된 데이터
value = 7
print(bisect(data, value))
위의 코드는 주어진 배열(data) 속 찾고자 하는 값(value)의 인덱스를 반환하는 알고리즘이다. 배열을 반으로 나누어 탐색하는 이진 탐색 알고리즘은 배열의 크기가 두 배로 증가할 때마다 수행해야 하는 연산의 수가 한 번만 증가하기 때문에, 탐색 횟수는 O(log N)의 시간 복잡도를 따른다.
반면, 배열의 인덱스를 0부터 차례대로 1씩 증가시키며 값을 비교하는 선형 탐색 O(N)은 입력 크기 N이 증가함에 따라 연산 횟수도 선형적으로 증가하게 되며, 이로 인해 성능이 급격히 저하되는 문제를 초래한다.
# 선형 탐색
def linear(data, value):
n = len(data)
for i in range(n): # 인덱스를 0부터 차례로 증가시킴
if data[i] == value:
return i
return -1
data = [1, 3, 5, 7, 9, 11, 13, 15]
value = 7
print(linear(data, value))
아래는 선형 탐색과 이진 탐색의 탐색 횟수를 비교한 표이다.
| 배열 크기 N | 선형 탐색 | 이진 탐색 |
| 2 | 2 | 1 |
| 4 | 4 | 2 |
| 128 | 128 | 7 |
| 1024 | 1024 | 10 |
| 65536 | 65536 | 16 |
동일한 기능을 수행하는 두 알고리즘이라 하더라도, 요구되는 입력의 크기와 필요한 자원에 따라 효율성은 크게 달라지게 된다. 따라서, 시간 복잡도가 적은 적절한 알고리즘을 선택하여 프로그램을 개발하는 것이 문제 해결에서 가장 중요하다고 말할 수 있다.
마치며
알고리즘 문제를 해결할 때에는 가독성을 해치지 않는 선에서 최대한 복잡도가 낮게 프로그램을 작성하는 것이 중요하다. 빅오 표기법은 알고리즘의 성능을 비교하고, 최적의 알고리즘을 선택하는 데 중요한 역할을 한다.