시간 복잡도(Time Complexity), 빅-오(Big-O) 표기법
알고리즘 문제풀이의 핵심은 효율적인 방법을 고민하는 것이다.
효율적인 방법을 고민한다는 것은 시간 복잡도를 고민한다는 것과 같다.
시간 복잡도
입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?
알고리즘 스피드는 "완료까지 걸리는 절차의 수"로 결정된다.
효율적인 알고리즘 구현이란 곧, 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘이다.
시간 복잡도는 주로 Big-O 표기법을 사용해 나타낸다.
선형검색(Linear Search)은 사이즈가 N개면, N스텝이 필요하다는 말을
선형검색의 시간 복잡도 = O(N) 이라고 표현하는 것이 Big-O 표기법이다.
Big-O 표기법
시간 복잡도를 표기하는 세가지 방법이 있다.
- Big-O(빅-오): 최악의 경우
- Big-Ω(빅-오메가): 최선의 경우
- Big-θ(빅-세타): 중간(평균)의 경우
알고리즘 구현에 있어 최악의 경우를 고려하여 대비하는 것이 바람직하다. 그래서 Big-O 표기법을 많이 사용한다.
O(1)
constant complexity(일정한 복잡도)라고 하며, 입력값(input size)이 증가하더라도 시간이 늘어나지 않는다.
입력값의 크기과 무관하게 미리 정해진 스텝에 따라 작동한다. 상수(constant)에 신경쓰지 않는다. 즉시 출력값을 얻어낼 수 있다.
function printFirst(arr) {
console.log(arr[0])
console.log(arr[0]) // 2번 출력하는 함수라고 해도 O(1) -> 상수는 신경안씀
}O(n)
linear complexity(선형 복잡도)라고 하며, 입력값이 증가함에 따라 시간도 같은 비율로 증가하는 것을 의미한다. 선형검색과 비슷하다.
function printAll(arr) {
for (let i of arr) {
console.log(i);
}
}O(log n)
logarithmic complexity(로그시간 복잡도)라고 부르며, Big-O 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
BST(Binary Search Tree, 이진검색)알고리즘을 설명할 때 사용한다. -> 인풋값이 2배 증가해도 스텝은 1밖에 증가하지 않는다.
Big O의 특성상 log의 base는 생략한다.
O(n²)
O(n²)은 quadratic complexity(이차시간 복잡도)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.
예를 들어, 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면, 이 알고리즘의 시간 복잡도는 O(n²)라고 표현한다.
n이 커지면 커질수록 지수가 주는 영향력이 점점 퇴색되기 때문에 모두 O(n²)이라고 표기한다.
O(2ⁿ)
exponential complexity(지수시간 복잡도)라고 부르며, Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.
n이 하나 증가할 때 마다, 걸리는 시간이 그 전보다 2배씩 걸리는 알고리즘이다.
구현한 알고리즘의 시간복잡도가 O(2ⁿ)이라면 다른 접근 방식을 고민해봐야 할 것이다.
