시간복잡도란?
- 알고리즘의 연산에 걸리는 시간을 뜻하는 것으로, 말 그대로의 시간이 아닌 연산횟수를 고려한다.
- 시간 복잡도를 표현하는 방식에는
Big-O(빅 오), Big-Ω(빅 오메가), Big-θ(빅 세타) 가 있으며, 각각 최악의 경우, 최선의 경우, 평균적인 경우를 고려한다.
Big-O
- 가장 자주 사용되는 표현방식.
- 최악의 상황을 고려하므로, 의도치 않은 긴 연산까지 고려한다.
O(1)
- 입력값이 변화한다고 해도 그 시간이 늘어나지 않는 연산을 이야기한다.
- 이를 변하지 않는다고 하여
상수복잡도(Constant Complexity) 라고 이야기한다.
- 예시로 인덱스를 이용하여 데이터를 얻는 방식을 들 수 있다.
→ 즉시 값을 출력한다.
O(n)
- 입력값의 증가에 따라 그 시간이 같은 비율로 증가하는 것을 의미한다.
→ 1개에 1초가 걸렸다면, 100개에는 100초가 걸린다.
- 이를
Linear Complexity 라고 한다.
- 만약 2배(2n), 5배(5n)로 늘어난다고 해도, 일정하게 늘어가는 것이므로 똑같이
O(n)으로 표기한다.
- 예시로
반복문을 들 수 있다.
→ 배열의 길이가 늘어날 수록 연산시간이 길어진다.
O(log n)
- 연산이 진행되면서 시간의 증가비율이 절반으로 점점 줄어드는 것을 이야기한다.
→ O(1) 다음으로 빠른 시간복잡도를 가진다.
Logarithmic Complexity 라고 하며, 뭐 Log의 성질을 가진 복잡도를 가진다고 생각하자...- 예시로
BST 탐색이나, 이분탐색을 들 수 있다.
O(n^2)
- 입력값의 증가에 따라 시간의 비율이 제곱수의 비율로 증가하는 것을 의미한다.
→ 1개가 1초가 걸렸는데, 10개를 넣으니 100초가 걸리는 경우.(n^2)
- 이를
Quadratic Complexity 라고 한다.
O(n)과 마찬가지로 지수가 늘어난다고 해도 동일하게 O(n^2)라고 표현한다.
→ O(n^5) 라고 이야기 하지 않고, 무조건 O(n^2) 라고 한다.- 예시로
다중 반복문을 들 수 있다.
O(2^n)
- 가장 느린 시간복잡도로, 시간이 제곱으로 늘어난다.
→ 1개가 1초가 걸렸다면 10개는 1024초가 걸리는 경우(2^n)
- 이를
Exponential Complexity 라고 한다.
- 만약 작성한 알고리즘이 해당 시간복잡도를 가진다면 다른 방법을 고려하는 것이 좋다.
