시간 복잡도

시간 복잡도

특정 알고리즘이 문제를 해결하는 데 필요한 컴퓨터 자원 중 하나인 '시간'을 측정하는 방법입니다. 알고리즘의 시간 복잡도는 입력의 크기에 대한 알고리즘의 실행 시간을 나타냅니다. 이를 표기하는 데에는 대게 Big O 표기법이 사용됩니다.

시간 복잡도	의미
O(1)	상수 시간(constant tiem)
O(logN)	로그 시간(log time)
O(N)	선형시간(linear time)
O(NlogN)	로그 선형 시간(log-linear time)
O(N^2)	이차 시간(quadratic time)
O(N^3)	삼차 시간(cubic time)
O(2^N)	지수 시간(exponential time)

O(1): 상수 시간(constant time)
상수 시간 복잡도를 가지는 알고리즘은 입력 크기에 관계없이 항상 일정한 시간이 걸립니다. 예를 들어, 배열에서 특정 인덱스의 값을 찾는 작업은 O(1)의 시간 복잡도를 가집니다.

O(logN): 로그 시간(log time)
로그 시간 복잡도를 가지는 알고리즘은 입력 크기를 계속해서 절반으로 줄여나갑니다. 이런 알고리즘의 대표적인 예는 이진 검색(Binary Search)입니다. 입력 크기가 두 배가 되어도, 한 단계만 더 거치면 되기 때문에 매우 효율적입니다.

O(N): 선형시간(linear time)
선형 시간 복잡도를 가지는 알고리즘은 입력 크기에 비례해서 시간이 증가합니다. 예를 들어, 배열에서 최대값을 찾거나 모든 원소를 더하는 등의 작업은 O(N)의 시간 복잡도를 가집니다.

O(NlogN): 로그 선형 시간(log-linear time)
로그 선형 시간 복잡도를 가지는 알고리즘은 입력 크기에 비례하되, 그 비율이 로그를 따릅니다. 병합 정렬(Merge Sort)이나 힙 정렬(Heap Sort) 등의 정렬 알고리즘이 O(NlogN)의 시간 복잡도를 가집니다.

O(N^2): 이차 시간(quadratic time)
이차 시간 복잡도를 가지는 알고리즘은 입력 크기의 제곱에 비례하여 시간이 증가합니다. 버블 정렬(Bubble Sort)이나 선택 정렬(Selection Sort) 등이 O(N^2)의 시간 복잡도를 가집니다.

O(N^3): 삼차 시간(cubic time)
삼차 시간 복잡도를 가지는 알고리즘은 입력 크기의 세제곱에 비례하여 시간이 증가합니다. 이런 시간 복잡도를 가지는 알고리즘은 비교적 드뭅니다. 3차원 데이터를 처리하거나, 행렬의 곱셈 등에서 볼 수 있습니다.

O(2^N): 지수 시간(exponential time)
지수 시간 복잡도를 가지는 알고리즘은 입력 크기에 대해 시간이 기하급수적으로 증가합니다. 피보나치 수열의 재귀적 계산 등이 이에 해당하며, 일반적으로 이러한 알고리즘은 매우 비효율적이라 할 수 있습니다.