시간 복잡도 (Time complexity)
입력 값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비례하여 시간이 얼마나 걸리는가?
즉 입력 값이 커짐에 따라 증가하는 시간의 비율을 말한다.
시간 복잡도 표기
- Big-O(빅-오)
- Big-Ω(빅-오메가)
- Bid-θ(빅-세타)
세가지 표기법은 최악, 최선, 중간(평균)의 경우를 나타내는 방법이다.
빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간을 고려할 수 있다.
<빅-오 표기법>
O(1) - constant complexity
입력값이 증가하더라도 시간이 늘어나지 않는다.
상수의 시간 복잡도이기 때문에, 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다.
예) 배열의 길이가 백만 단위로 늘어나더라도, 인덱싱을 통해 값을 즉시 알 수 있다.
O(n) - linear complexity
입력 값이 증가함에 따라 시간 또한 선형적으로, 같은 비율로 증가하는 것을 의미한다.
입력값이 1일 때, 1초의 시간이 걸리고, 입력값을 100배로 증가시킬 때는 100초의 시간이 걸리는 알고리즘의 경우 O(n) 시간 복잡도를 가진다고 말한다. 계수는 입력값이 커지면 영향력이 없어지기 때문에 표기하지 않는다.
O(log n) - Logarithmic complexity
빅오 표기법 중 O(1) 다음으로 빠른 시간 복잡도이다.
BST(Binary Search Tree) 의 경우, 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어드는데, 이런 경우를 O(log n)의 시간 복잡도를 가진다고 말한다.
O(n2) - quadratic complexity
입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.
예를 들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면, 이 알고리즘의 시간 복잡도는 O(n2)라고 표현합니다.
O(2n) - Exponential complexity
빅오 표기법중 가장 느린 시간 복잡도를 가진다.
종이를 42번 접으면 그 두께가 지구에서 달까지의 거리보다 커진다는 하는데, 고작 42번 만에 얇은 종이가 그만한 두께를 가질 수 있는 것은 매번 접힐 때마다 두께가 2배로 늘어나기 때문이다.
이와 같은 시간 복잡도라고 이해하면 되고, 구현한 알고리즘의 시간 복잡도가 O(2n)이라면 다른 접근 방식을 고민해 보는 것이 좋다.
