즉 최악의 상황에서도 이 정도의 성능은 보장할 수 있다는 것을 알려주는 것이 더 유용하다.
대부분의 알고리즘에서 평균의 경우와 최악의 경우는 같다.
가끔 다르기도 하지만 그럼에도 최악의 경우를 보는 것이 최선이다.
주로 쓰이는 Big - O (빠른 순)
O(1)
상수 시간
O(log N)
로그 시간
O(N)
직선적 시간
O(N logN)
N 로그 N 시간
O(N^2)
2차 시간
O(2^N)
지수 시간
이 중, 로그 시간과 지수 시간에 대한 설명을 작성해보겠다.
O(2^n) 피보나치수열을 표현한다면, O(2^n)을 표현할 수 있다.
피보나치수열은 다음 그림과 같다.
이것을 코드로 구현한다면?
function a(n) {
if (n <= 0) {
return 0;
} else if (n === 1) {
return 1;
}
return a(n - 1) + a(n - 2);
}
피보나치 수열을 구하는 코드를 재귀 함수를 통해 구현하였다.
즉, 함수를 호출할 때마다 바로 전 숫자와 그 전 숫자를 알아야 숫자를 더하면서 앞으로 나올 숫자를 파악할 수 있다. 이렇게 매번 함수가 호출될 때마다 두 번씩 호출한다. 이걸 n의 크기만큼 반복한다.
따라서 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)
}
}
}
이렇게 한 번 처리할 때마다 검색해야 하는 데이터의 양이 절반씩 떨어지는 알고리즘을 로그 시간 알고리즘이라고 한다.
이 방법을 활용한다면 수 많은 데이터가 존재해도 성능은 크게 차이 나지 않을 것이다.
Big - O 계산법
계수는 버려라 O(2N)은 O(N)으로 표기할 수 있다. 빅오는 처리 시간의 증가율을 알려주는 것이기 때문에 계수를 쓰는 것은 쓸모가 없다. 즉, 빅오는 정확한 속도를 계산하려고 하는 것이 아니다!
식의 차수/우세한 항을 이용하라 만약 함수 표현이 다항식이라면, 식의 차수가 제일 높은 항이나 우세한 항으로 빅오를 표기하면 된다.
우세한 항을 구분하지 못하는 경우, O(A + B)와 같이 다항식으로 빅오를 표현할 수도 있다.
덧셈 vs 곱셈
for (x in arrayX) {
console.log(x);
}
for (y in arrayY) {
console.log(y);
}
위의 예시는 x만큼 실행한 후 y만큼 실행한다. 그러므로 시간 복잡도는 O(x + y)이다.
for (x in arrayX) {
for (y in arrayY) {
console.log(x + "," + y);
}
}
위의 예시는 y만큼의 실행을 x만큼 실행한다. 따라서 시간 복잡도는 O(x * y)이다.
로그 런타임 (log N)
로그로 표현되는 알고리즘들은 대부분 문제가 반토막이 나는 경우이다. Binary Search와 같이 문제의 크기가 계속 절반으로 작아지는 경우 O(log N)으로 표현한다.
