복잡도는 알고리즘의 성능을 나타내는 척도입니다.
시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미합니다. 또한 시간적 개념이 아니라 연산 횟수를 기준으로 가장 최악의 상황을 계산합니다. 시간 복잡도 계산에서 상수항은 무시합니다. 상수항을 무시하는 이유는 알고리즘의 실행시간을 대표하는 요소가 연산의 총횟수이기 때문입니다. 따라서 시간 복잡도 분석에서는 주요한 비교 대상인 연산의 총횟수에 초점을 맞추기 위해 상수항을 무시하고 최악의 경우를 고려하여 계산합니다. 표기법은 O( )로 표기합니다.
<aside> 💡 N = 입력된 수
O(1) : 상수 시간
O(logN) : 로그 시간
O(N) : 선형 시간
O(NlogN) : 선형 로그 시간
O($N^2$) : 제곱 시간
O($2^N$) : 지수 시간
O(1) < O(logN) < O(N) < O(NlogN) < O($N^2$) < O($2^N$)
</aside>
O(1)는 상수시간을 의미하고 입력 크기에 상관없이 일정한 실행 시간이 소요됩니다. 아래 예제를 보면 배열의 첫 번째 요소를 반환하는 함수입니다. 이 함수의 실행 시간은 항상 첫 번째 요소를 반환하는 한 번의 연산을 수행하므로 입력 크기와 관계없이 상수 시간이 소요됩니다. 즉, 실행 시간은 일정하기 때문에 입력 크기가 변해도 실행시간에는 영향을 주지 않습니다.
import timeit
import random
def bigO_1 (배열):
return 배열[0]
측정코드 = "bigO_1 ([1, 2, 3, 4])"
실행시간 = timeit.timeit (stmt=측정코드, globals=globals(), number=1)
print (f'실행시간 : {실행시간}')
<aside> 💡 < 실행 결과 >
실행시간: 2.42200076172594e-06
</aside>
입력 크기에 비례하여 실행 시간이 증가하지만, 그 속도는 로그에 비례합니다. 입력 크기가 2배로 증가할 때마다 실행시간이 약간 늘어납니다. 아래 예제를 보면 이진 검색을 사용하여 배열에서 대상 값을 찾는 함수입니다. 이진 검색은 입력 크기 N에 대해 탐색 범위를 반씩 줄여가기 때문에 탐색에 필요한 연산 횟수가 로그의 형태로 증가합니다. 예를 들어 배열의 크기가 16일 경우 최대 4번의 비교가 필요합니다. 이처럼 입력 크기에 대해 로그의 형태로 비교 횟수가 증가하기 때문에 O(logN)이 됩니다.
import timeit
import random
def bigO_logN (배열, 대상):
l = 0
h = len(배열) - 1
while l <= h:
m = (l + h) // 2
if 배열[m] == 대상:
return m
elif 배열[m] < 대상:
l = m + 1
else:
h = m - 1
return -1
배열 = [random.randint(1, 1000) for _ in range(1000)]
측정코드 = "bigO_logN (배열,3)"
실행시간 = timeit.timeit (stmt=측정코드, globals=globals(), number=1)
print (f'실행시간 : {실행시간}')
<aside> 💡 < 실행 결과 >
실행시간 : 7.94200059317518e-06
</aside>
입력 크기에 비례하여 실행시간이 증가합니다. 아래 예제를 보면 for 문을 통해 배열의 요소를 한 번씩 순회하며 하나씩 출력하는 함수입니다. 이 함수의 실행시간은 입력 크기에 비례하여 선형적으로 증가하기 때문에 입력 크기가 2배로 증가하면 실행시간도 2배로 증가합니다.