시간 복잡도
시간 복잡도란?
간단하게 알고리즘의 성능을 확인하는 것
입력값이 커집에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성
Big-O 표기법
-
Big-O 최악의 시간값
-
Big-Ω 최선의 시간값
-
Big-θ 평균의 시간값
Big-O 이 가장 많이 쓰이는 이유
최악의 상황을 고려해서 작성하는 것이 다양한 상황에 대응하기 좋다.
최선의 상황을 고려했다가 최선의 상황을 벗어난 경우가 생길 경우 새로이 조정을 해야하지만 최악의 경우를 고려한 뒤 그렇지 않을 경우을 생각하는 것이 더 합리적이기 때문이다. 무조건 최선의 상황이 나온다는 보장이 없기 때문에
Big-O 표기법의 종류
- O(1)
입력값의 변화 유무와 상관없이 일관된 시간을 가지는 경우
function (n) {
return 'Hi'
}위의 경우 n이 어떠한 인자나 들어가더라도 항상 일관된 시간으로 리턴값은 문자열 'Hi'가 출력된다.
- O(n)
입력값의 변화에 따라 시간 역시 같은 비율로 증가하는 경우
let arr = [1,2,3]
function (arr) {
for (let i = 0; i<arr.length; i++) {
arr[i] = arr[i] * 2
}
}위의 경우 arr의 크기가 3일때 반복되는 경우가 3번이고 크기가 4라면 반복은 4번반복되며 크기가 n일 경우 n번 반복됨을 통해 입력값(예시의 배열)이 변화 할 때 시간 역시 같이 증가하게 된다.
- O(log n)
입력값의 변화에 따라 시간이 O(n)의 시간보다 시간이 덜 증가하게 됨
Up & Down 게임을 생각해보면 쉽게 알 수 있다.
100의 숫자 중 어떤 임의의 수 1개를 찾을 때
50보다 크냐 작냐를 따져서 클 경우 51~100 까지 중의 숫자를 찾으면 되는 것이고
작을 경우 1~50의 숫자를 찾으면 되기 때문에 처음 100개의 숫자 중에서 찾는것이 아닌 절반의 수 50개의 숫자에서 임의의 숫자를 찾게 됨.
이렇게 경우의 수를 절반씩 줄어들기 때문에 O(1) 다음으로 효율적인 시간 복잡도
- O(n^2)
입력값의 변화에 따라 시간의 입력값의 제곱의 비율로 증가
function (n) {
for (let i =0; i<n; i++) {
for (let j = 0; j<n; j++) {
//임의의 식
}
}
}위의 경우 i가 0일때 j가 n만큼의 수를 반복해야하고 i가 1일 때 j가 n만큼의 수를 반복해야하고...
결과적으로 n^2 만큼 반복하게 되는 경우로 만약 반복문이 3개라면 n^3 5개라면 n^5 로 걸리는 시간이 기하급수적으로 늘어날 수 있다.
- O(2^n)
Big-O표기법 중 가장 느린 시간 복잡도
입력값의 변화에 따라 시간이 2^입력값의 비율로 증가
function fibonacci(n) {
if (n < 2) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}대표적인 예시가 피보나치 수열
입력값 5을 구하기 위해서 입력값 4와 3을 알아야하고 4를 알기 위해서 3,2 3을 알기위해서 2,1...
굉장히 오랜시간으로 알아내야 알 수 있는 방법이기 때문에 시간복잡도가 O(2^n) 이라면 다른 접근 방식 고민 추천
Greedy Algorithm
탐욕 알고리즘은 결정의 순간마다 당장 눈앞에 보이는 최적의 상황만을 탐욕적으로 쫓아 최종적인 해답에 도달하는 방법
- 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택
- 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사
- 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 1번으로 돌아가 위의 과정을 반복
탐욕 알고리즘을 사용하려면 문제가 아래의 2가지 조건을 성립하여야 잘 작동
- 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않아야함
- 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성
Dynamic Programming
이 알고리즘은, 탐욕 알고리즘과 다이내믹 프로그래밍 모두 작은 문제에서부터 출발한다는 점은 같지만, 탐욕 알고리즘이 순간의 최적을 찾는 방식이라면, Dynamic Programming은 모든 경우의 수를 따져본 후 이를 조합해 최적의 해법을 찾는 방식
두 가지 가정이 만족하는 조건에서 사용할 수 있다.
- 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제들은 중복된다. (Overlapping Sub-problems)
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다. (Optimal Substructure)
첫 번째 조건인 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제들은 중복된다 (Overlapping Sub-problems) 는 바꿔말하면 큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러 번 반복해서 사용될 수 있어야 한다 라고 할 수 있다.
예를 들어 피보나치의 경우 구하고자 하는 n번째의 숫자는 n-1 과 n-2의 합이고
n-1 번째 숫자는 n-2 와 n-3 의 합이기 때문에 가장 밑에 있는 0 , 1(작은문제) 부터 차례대로 답을 구하고 정답(큰 문제)에 작은 문제를 통해 풀어나가는 것
Dynamic Programming 하는법 2가지
- Recursion + Memoization (top down)
- Iteration + Tabulation (bottom up)
Recursion + Memoization (top down)
재귀를 이용한 다이나믹 프로그래밍
function fibonacci(n) {
let arr = [0, 1];
const recursion = (count = 2) => {
arr.push(arr[count-2] + arr[count-1]);
if(count === n) {
return;
}
recursion(count + 1);
}
if(n === 0) {
return 0;
}
else if(n === 1) {
return 1;
}
else {
recursion();
return arr[n];
}
}arr 에 한번 만들어낸 피보나치(n)을 저장하고 필요할때마다 꺼내 씀 memoization을 사용하는 방법이다.
하위 문제의 해결책을 저장한 뒤 동일한 하위 문제가 나왔을 경우 저장해 놓은 해결책을 이용한다
Iteration + Tabulation (bottom up)
반복문을 이용한 다이나믹 프로그래밍
재귀 함수를 이용한 방법은 문제를 해결하기 위해 큰 문제부터 시작하여 작은 문제로 옮아가며 문제를 해결하였다면, 반복문을 이용한 방법은 작은 문제에서부터 시작하여 큰 문제를 해결해 나가는 방법
function fibTab(n) {
if(n <= 2) return 1;
let fibNum = [0, 1, 1];
// n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다
for(let i = 3; i <= n; i++) {
fibNum[i] = fibNum[i-1] + fibNum[i-2];
// n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여
// n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다
}
return fibNum[n];
}자료구조는 정말 어렵다... 열심히 익히자
