시간 복잡도란?
시간 복잡도는 알고리즘이 실행될 때 입력값의 크기에 따른 연산 횟수를 일종의 함수로 표현한 것이다.
이 때, 실행 시간은 프로세서의 성능과 언어에 따라 천차만별이 되기 때문에 보다 정량적인 비교를 위하여 연산 횟수를 척도로 삼은 것이다.
Big-O Notation이란?
알고리즘은 그 입력값의 크기에 따른 연산 횟수의 고유의 성장률을 가진다.
알고리즘 실행 결과의 최악의 경우(탐색 알고리즘의 경우, 탐색 대상이 탐색 순서 상 가장 마지막에 위치한 경우)그 성장률에서 가장 큰 영향을 주는 항만 분리해 내어 일종의 함수로 표기한 것이 Big-O Notation이다.
이 때, 가장 큰 영향을 주는 항 앞의 계수는 무시한다.
Big-O Notation은 O(n에 대한 시간복잡도)의 꼴으로 표기하며, 다음은 그 형태들이다.
-
과 같은 상수(constant) 형태
-
O(log n)과 같은 로그(logarithmic) 형태
-
O(n)과 같은 선형(linear)
-
과 같은 선형로그 형태
-
과 같은 다차(polynomial) 형태
-
과 같은 지수(exponential) 형태
-
과 같은 팩토리얼(factorial) 형태
예를 들어, 시간 복잡도가 O(n)인 알고리즘의 입력값의 크기가 n이라면 알고리즘의 연산 횟수는 n에 비례하게 되는 식이다.
결론
시간 복잡도의 개념은 입력값의 크기가 매우 커졌을 때 큰 힘을 발휘한다.
n = 3이면 O(n)의 복잡도 = 3, O(2^n)의 복잡도 = 8으로 큰 차이가 없지만,
n = 100이 되면 O(n)의 복잡도 = 100, O(2^n)의 복잡도 = 약 1.267 * 10^30으로 천문학적인 차이가 발생하게 된다.
따라서 큰 입력값을 시간 복잡도가 높은 알고리즘을 통해 처리하고자 한다면 시간적으로 대단히 불리해짐을 알 수 있다.
시간 복잡도는 일종의 알고리즘의 "비용"과 같은 개념이며, Big-O Notation은 그를 표기하는 하나의 방법인 것이다.