Time Complexity
입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?
효율적인 알고리즘이란 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 이야기이다.
시간 복잡도는 주로 빅-오 표기법으로 사용해 나타낸다.
시간 복잡도 표기 방법
- Big-O(빅오)
- Big-Ω(빅-오메가)
- Big-θ(빅-세타)
세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다.
빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다.
"이 정도 시간까지 걸릴 수 있다"를 고려해야 그에 맞는 대응이 가능하다.
최선의 경우 또는 평균값을 기대하는 시간 복잡도로 알고리즘을 구현한다면, 최악의 경우 어디에서 문제가 발생했는지 알아내기 위해 로직의 많은 부분을 파악해야 하므로 문제를 파악하는 데 많은 시간이 필요하다.
그래서, 최악의 경우에도 고려하여 대비하는 것이 바람직하기 때문에, 다른 표기법보다 Big-O 표기법을 많이 사용한다.
O(1)
Big-O 표기법은 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?를 표기하는 방법이다.
O(1)은 constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다. 다시 말해 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다.
function O_1_algorithm(arr, index) {
return arr[index];
}
let arr = [1, 2, 3, 4, 5];
let index = 1;
let result = 0_1_algorithm(arr, index);
console.log(result); // 2위 예시의 경우, arr의 길이가 100만이라도, 즉시 해당 index에 접근해 값을 반환할 수 있다.
O(n)
O(n)은 linear complexity라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.
입력값이 1일 때 1초의 시간이 걸리고, 입력값을 100배로 증가시켰을 때 1초의 100배인 100초가 걸리는 알고리즘의 경우, O(n)의 시간 복잡도를 가진다.
function O_n_algorithm(n) {
for(let i = 0; i < n; i++) {
// do something for 1 second
}
}
function another_O_nalgorithm(n) {
for(let i = 0; i < 2n; i++) {
// do something for 1 second
}
}O_n_algorithm함수에선 입력값(n)이 1씩 증가할 때마다 실행 시간이 1초씩 증가한다. 입력값이 증가함에 따라 같은 비율로 걸리는 시간이 늘어난다.
another_O_n_algorithm은 n이 1씩 증가할 때마다 실행 시간이 2초씩 증가한다.
여기서, another_O_n_algorithm의 시간 복잡도는 O(2n)이 되지 않고, O(n)으로 표기한다.
입력값이 커지면 커질수록 계수의 영향력이 퇴색되기 때문에, 같은 비율로 증가하고 있다면 모두 O(n)으로 표기한다.
O(log n)
O(log n)은 Logarithmic complexity라고 부르며 빅오 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
BST(Binary Search Tree) 의 경우, 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다.
이 경우 O(log n)의 시간 복잡도를 가진 알고리즘이다.
O(n²)
O(n²)은 ``quadratic complexity``라고 부르며, 입력값이 증가함에 따라 시간이 ndml 제곱수의 비율로 증가하는 것을 의미한다.
예를 들어 입력 값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면, 이 알고리즘의 시간 복잡도는 O(n²)라고 표현한다.
function O_quadratic_algorithm(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
// do something for 1 second
}
}
}
function another_O_quadratic_algorithm(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
for (let k = 0; k < n; k++) {
// do something for 1 second
}
}
}
}2n, 5n 을 모두 O(n)이라고 표현하는 것처럼 n³과 n⁵도 모두 o(n²)로 표기한다. n이 커지면 커질수록 지수가 주는 영향력이 점점 퇴색되기 때문에 이렇게 표기한다.
위 예시의 경우로 보면, 입력값을 5를 주게되면, 내부 반복문에서 5초의 시간이 걸리고, 그 반복문을 나와 외부 반복문을 수행하게 된다. 즉, 내부 반복문이 5번 실행되는 것이므로, 25초가 걸리게 된다.
반복문이 세번 모두 중첩된 경우, 5³초가 걸리게 된다.
이 경우들 모두 O(n²)의 시간 복잡도를 가진다.
O(2ᴺ)
O(2ᴺ)는 exponential complexity라고 부르며 Big-O 표기법 중 가낭 느린 시간 복잡도를 가진다.
종이를 42번 접으면 그 두께가 지구에서 달까지의 거리보다 커진다는 이야기를 들어본 적이 있으신가요?
고작 42번 만에 얇은 종이가 그만한 두께를 가질 수 있는 것은, 매번 접힐 때마다 두께가 2배로 늘어나기 때문입니다.
구현한 알고리즘의 시간 복잡도가 O(2ᴺ)라면 다른 접근 방식을 고민해보는 것이 좋다.
function fibonacci(n) {
if (n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}재귀로 구현하는 피보나치 수열은 O(2ᴺ)의 시간 복잡도를 가진 대표적인 알고리즘이다.
브라우저 개발자 창에서 n을 40으로 두어도 수초가 걸리는 것을 확인할 수 있으며, n이 100 이상이면 평생 결과를 반환받지 못할 수도 있다.
