시간 복잡도
시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
시간 복잡도
시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다.
작성 방법에 따라 걸리는 시간이 달라지며, 시간이 적게 걸리는 것이 좋은 소스이다.
시간 복잡도에는 빅-오 표기법이라는 개념이 나온다.
예를 들어, 동전을 던져 뒷면이 나올 확률을 얘기 할 때 운이 좋으면 1번에 뒷면이 나오지만
운이 안 좋다면 n번 만큼 동전을 던져야 하는 경우가 발생한다.
이 최악의 경우를 계산하는 방식을 빅-오(Big-O) 표기법이라 부른다.
O(1)
Constant Time (상수)
입력 데이터 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘.
function getFirstElement(array) {
return array[0];
}O(n)
Linear Time (선형)
입력 데이터 크기에 비례해 처리 시간이 걸리는 알고리즘.
n이 1번 늘어날 때마다 처리시간이 1 증가하여 선형적으로 증가함. (n 크기만큼 처리시간이 증가)
function sumArray(array) {
let sum = 0;
for (let i = 0; i < array.length; i++) {
sum += array[i];
}
return sum;
}O(n^2)
Quadratic Time
입력 데이터 n만큼 반복하는데, 그 안에서 n만큼 또 반복할 때의 표기 방법.
데이터가 적을 때는 문제가 없지만 많아질수록 수직상승한다.
function sumArray(array) {
let sum = 0;
for (let i = 0; i < array.length; i++) {
for (let j = 0; j < array[i].length; j++) {
sum += array[i][j];
}
}
return sum;
}n만큼 반복하면서 그 안에서도 n만큼 반복하여 처리횟수가 n을 가로와 세로 길이로 가지는 면적만큼 늘어나게 된다. n이 증가할 때마다 가로,세로 한 줄이 증가하므로 데이터가 커질수록 처리시간이 부담된다.
| 0 | 1 | ... | n |
| 1 | |||
| ... | |||
| n |
O(log n)
이진 탐색 등의 알고리즘을 표현할 때 사용한다.
let arr = [];
function log(k, s, e){
for(let i = s; i <= e; i++){
arr.push(i);
let m = (s+e)/2;
if(arr[m] === k){
console.log(m)
} else if(arr[m]> k){
return log(k, s, m-1);
} else{
return log(k, m+1,e)
}
}
}- 정렬된 배열에서 특정 숫자를 찾을 때, 이진 검색을 이용한다면 배열의 가운데 값과 키값을 비교한다.
- 만약 배열의 가운데 값이 키값보다 작다면, 키값보다 작은 값들은 볼 필요가 없다.
- 그럼 다시 없어진 배열 값을 제외한 elements들 중에서도 중간값을 찾아서 키값과 비교한다.
- 이렇게 한번 처리할 때마다 검색해야 하는 데이터의 양이 절반씩 떨어지는 알고리즘을 O(log n) 알고리즘이라 한다.
이와같은 방법을 활용한다면, 수많은 데이터가 존재해도 성능은 크게 차이 나지 않는다.
O(nm)
Quadratic Time
O(n^2)와 비슷하지만 다르다. n만큼 2번 반복하는 것이 아닌, n을 m만큼 반복한다.
n > m 또는 n < m 이런 상황이 발생할 수 있다.
function compareArrays(array1, array2) {
var n = array1.length;
var m = array2.length;
var foundMatch = false;
// O(nm) 비교
for (var i = 0; i < n; i++) {
for (var j = 0; j < m; j++) {
if (array1[i] === array2[j]) {
foundMatch = true;
break;
}
}
if (foundMatch) {
break;
}
}
return foundMatch;
}O(n^2)랑 비슷하지만 n이 엄청 클수도 있고, m이 엄청 작을 수도 있다.
따라서 그래프도 O(n^2)랑 비슷하지만 상황에 따라 다르게 그려진다.
| 0 | 1 | ... | n |
| ... | |||
| m |
O(n^3)
Polynomial / Cubic Time
n을 3중으로 반복한다. 따라서 큐빅과 같은 구조를 띈다.
function matrixMultiplication(matrixA, matrixB) {
var n = matrixA.length;
var m = matrixB[0].length;
var result = [];
// O(n^3) 행렬 곱셈
for (var i = 0; i < n; i++) {
result[i] = [];
for (var j = 0; j < m; j++) {
var sum = 0;
for (var k = 0; k < matrixB.length; k++) {
sum += matrixA[i][k] * matrixB[k][j];
}
result[i][j] = sum;
}
}
return result;
}
O(n)일 때 직선 (1차원)
O(n^2) 일 때 면적 (2차원)
O(n^3) 일 때 큐빅 (3차원)
데이터가 증가할 때마다 급격하게 처리시간이 늘어난다.
O(2^n)
Exponential Time
피보나치(Fibonacci) 수열로 비유할 수 있다.
function fibonacci(n) {
if (n < 2) {
return n;
}
// O(2^n) 피보나치 수열
return fibonacci(n - 1) + fibonacci(n - 2);
}매번 함수가 호출될때마다 2번씩 호출하게 된다.
이 호출하는 횟수는 피보나치 수열 트리 구조의 높이만큼 반복된다. 따라서 O(2^n)의 시간 복잡도를 갖는다.
