TIL-41, Big-O 표기법
알고리즘 문제를 풀 땐 항상 시간 복잡도 를 고민해야 한다.
시간 복잡도를 고민한다는 것은, 효율적인 알고리즘의 방법을 고민한다는것과 같다.
입력값이 커짐에 따라 시간이 증가하는데, 이 증가하는 시간의 비율을 최소화한 알고리즘이 효율적인
알고리즘이다. 이러한 시간 복잡도를 빅-오 표기법으로 나타낸다.
Big-O 표기법
빅오 표기법은 최악의 경우를 고려해야한다.
한번의 결과를 반환하는데 최선의 경우 1초, 최악의 경우 100시간이 걸리는 알고리즘이 있다.
이 알고리즘을 100번 실행할 때, 최선의 경우 100초, 최악의 경우 10000시간이 걸린다.
최선의 경우를 고려해 이 알고리즘을 짰을 경우, 10000시간이 걸리는 최악의 경우가 발생했을 때
도대체 어디서 문제가 발생하는 것인지 알 수가 없다.
때문에 최악의 경우를 고려해 대비하는 것이 바람직하다.
O(1)
O(1)은 입력값이 증가해도 시간이 늘어나지 않는다.
즉, 입력값의 크기와 관계 없이 즉시 출력값을 얻어낼 수 있다.
function O_1(arr, index) {
return arr[index];
}
let arr = [1, 2, 3];
let index = [0];
console.log(O_1(arr, index)); // 1
위의 알고리즘에서 입력값이 100000000이어도, 즉시 해당 arr의 index의 값을 반환할 수 있다.
O(n)
O(n)은 입력값이 증가함에 따라 시간 역시 동일 비율로 증가하는 것을 의미한다.
입력값이 1일때 1초의 시간이 걸리고, 입력값이 100000일때 100000의 시간이 걸린다.
function O_n(n) {
for (let i = 0; i < n; i++) {
// 1초가 걸리는 행동
}
}
function another_O_n(n) {
for (let i = 0; i < 2n; i++) {
// 1초가 걸리는 행동
}
}
위와 같은 알고리즘을 O(n)의 시간복잡도를 가졌다고 말한다.
이 때, another_O_n 함수는 n이 1씩 증가할 때마다 실행 시간이 2초씩 증가하지만,
입력값이 커질수록 계수(n의 앞의 수)의 의미(영향력)가 점점 희미해지기 때문에,
같은 비율 로 증가하고 있다면 10배, 20배로 증가하더라도 O(n)이다.
O(log n)
O(log n)은 O(1) 다음으로 가장 빠른 시간 복잡도를 가진다.
반반 나눠가며 해답을 찾았던 BST (Binary Search Tree)처럼 말이다.
대학시절 술자리에서 자주 했던 게임 ‘Up & Down’ 을 생각하면 된다.
병뚜껑의 숫자는 1에서 50까지, 적힌 숫자는 6이라고 가정.
(1) 절반인 25를 외치고, Down을 외침.
(2) 다시 그 절반인 12를 외치고, Down을 외침.
(3) 다시 그 절반인 6을 외치면, 정답.
매번 숫자를 절반으로 뚝뚝 뗄때마다 경우의 수 역시 절반으로 줄어들기 때문에
최악의 경우여도 7번만에 원하는 숫자를 찾아낼 수 있다.
O(n^2)
O(n^2)은 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.
입력값이 1일때 1초가 걸리던 작업에 3이라는 값을 주었더니 9초가 걸리면, 이 알고리즘은
O(n^2)의 시간복잡도를 가졌다고 말한다.
function O_quadratic(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
// 1초가 걸리는 행동
}
}
}
function another_O_quadratic(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
for (let k = 0; k < n; k++) {
// 1초가 걸리는 행동
}
}
}
}
2n, 3n을 모두 O(n)이라고 표현하는 것처럼, n^3과 n^5역시 모두 O(n^2)로 표기한다.
n이 커지면 커질수록지수의 의미 (영향력이) 희미해지기 때문이다.
O(2^n)
O(2^n)은 빅오 표기법중 가장 느린 시간 복잡도를 가진다.
만약, 내가 구현한 알고리즘의 시간 복잡도가 이녀석이라면 다른 방법을 알아보도록 하자..
function fibonacci(n) {
if (n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
위 알고리즘처럼 재귀로 구현한 fibonacci는 O(2^n)의 대표적인 알고리즘이다.
n을 45로 해도 수십초가 걸리고, 만약 100 이상으로 둔다면 평생 답을 못얻을지도..
시간복잡도를 적절히 이용하기
입력 데이터가 클 때는 당연히 시간복잡도가 빠른 O(n) 또는 O(log n)의 알고리즘을 짜야 하지만,
입력 데이터가 작을 때는 시간복잡도가 크더라도 일단 문제를 풀어내자.
Greedy Algorithm
Greedy는 ‘탐욕스러운, 욕심 많은’ 이라는 뜻이다.
Greedy Algorithm(탐욕 알고리즘)은 말 그대로 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.
아래와 같은 단계로 구분할 수 있다
- 선택 절차 (Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
- 적절성 검사 (Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
- 해답 검사 (Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.
탐욕 알고리즘은 아래의 두가지 조건을 만족하는 ‘특정한 상황’이 아니면 최적의 해를 보장하지 못한다.
- 탐욕적 선택 속성 (Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않는다.
- 최적 부분 구조 (Optimal Substructure): 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
이처럼 탐욕 알고리즘은 항상 최적의 결과를 도출하는것은 아니지만, 어느정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다.
때문에 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.