알고리즘 평가 지표
- 정확성
- 작업량
- 메모리 사용량
- 최적성
- 효율성 - 시간 복잡도 / 공간 복잡도
코딩테스트 진행 시 많이 보게 되는 것이 메모리 사용량과 효율성 중에서도 시간 복잡도 부분이다.
시간 복잡도
효율적인 문제 해결방법을 고민한다는 것은 시간 복잡도를 고민한다는 것과 같다.
알고리즘의 로직을 코드로 구현할 때 시간 복잡도를 고려한다는 것은 ’입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?’ 라는 말이다.
즉, 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성한다는 말이다.
그리고 이 시간 복잡도는 주로 빅-오 표기법을 사용해 나타낸다.
시간 복잡도는 빅오, 세타, 오메가 세 가지 표기법으로 각각 최악, 평균, 최선의 경우에 대하여 나타낸다.
이 때 빅오 표기법이 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문에 자주 사용된다.
결과를 반환하는데 최선의 경우 1초, 평균적으로 1분, 최악의 경우 1시간이 걸리는 알고리즘을 구현했고, 최선의 경우를 고려한다고 가정해보자.
오메가 (Ω)
시간 복잡도의 최선의 경우를 고려한 경우
- 100번 실행 → 최선의 경우 100초 소요
- 이 때 실제로 걸린 시간이 1시간이 넘었다면, ’어디에서 문제가 발생한거지?‘란 의문이 생긴다.
- 최선의 경우만 고려하였으니, 어디에서 문제가 발생했는지 알아내기 위해서는 로직의 많은 부분을 파악해야 하므로 문제 파악하는데 많은 시간이 필요하게 된다.
세타 (Θ)
시간 복잡도의 평균의 경우를 고려한 경우
- 100번 실행 → 평균적으로 100분 소요
- 최악의 경우가 몇 개 발생하여 300분이 넘게 걸렸다면 최선의 경우를 고려한 것과 같이 문제 파악에 시간이 걸린다.
빅오 (O)
시간 복잡도의 최악의 경우를 고려한 경우
- 극단적인 예이지만, 위와 같이 최악의 경우를 발생하지 않기를 바라며 시간을 계산하는 것 보다는 ’최악의 경우도 고려하여 대비‘하는 것이 바람직하다.
- 따라서 다른 표기법보다 Big-O 표기법을 많이 사용한다.
👉 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가? 를 표기하는 방법이다.
빅오 표기법의 종류
- O(1)
- O(n)
- O(log n)
- O(n^2)
- O(2n)
O(1)
일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다. 즉, 입력값의 크기와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미이다.
function big_o(n) {
let sum = 0; // 1회
sum = n * 2; // 1회
return sum; // 1회
}3회 → O(1) : 상수
O(n)
선형 복잡도(linear complexity)라고 하며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.
예) 입력값 1개 → 1초 소요, 입력값 100개 → 100초 소요
function big_o(arr, n) {
let sum = 0; // 1회
// n회
for (let i = 0; i < n; i++) {
sum += arr[i];
}
return sum; // 1회
}
function big_o(arr, n) {
let sum = 0;
for (let i = 0; i < 2n; i++) {
// 2n 씩 실행 시
}
}n+2 → O(n)
*이때, 만약 2n 이라면 입력값이 1 증가할때마다 코드의 실행시간이 2초씩 증가한다. 그러면 이 알고리즘은 O(2n) 이라고 생각할 수도 있지만 이러한 알고리즘 또한 O(n) 으로 표현된다.
입력값이 커질수록 계수의 의미(영향력)가 퇴색되기 때문에 같은 비율로 증가하고 있다면 2배, 5배, 10배로 증가하더라도 O(n)으로 표기한다.
O(log n)
로그 복잡도(logarithmic complexity)라고 하며 , 빅오 표기법 중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
BST(Binary Search Tree)의 값 탐색 알고리즘이 O(log n)에 해당하는 시간 복잡도를 가진다.
❓ BST 탐색기법
원하는 값을 탐색할 때, 노드를 이동할 때 마다 경우의 수가 절반으로 줄어든다.
ex) UP & DOWN 게임
1. 1~100 중 하나의 숫자를 고른다. (30을 골랐다고 가정한다.)
2. 50 숫자를 제시하면 50보다 작으므로 down을 외친다.
3. 1~50중의 하나의 숫자이므로 또다시 경우의 수를 절반으로 줄이기 위해 25를 제시한다.
4. 25보다 크므로 up을 외친다.
5. 경우의 수를 계속 절반으로 줄여나가며 정답을 찾는다.
매번 숫자를 제시할 때마다 경우의 수가 절반이 줄어들기 때문에 최악의 경우에도 7번이면 원하는 숫자를 찾아낼 수 있게 된다.
function big_o(arr, n) {
let sum = 0; // 1회
// n / 2회
for (let i = 0; i < n; i *= 2) {
sum += 2;
}
return sum; // 1회
}n/2 + 2 → O(log n)
O(n^2)
2차 복잡도(quadratic complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.
예) 입력값 1 → 1초 소요, 입력값 5 → 25초 소요
function big_o(arr, n) {
let sum = 0; // 1회
// n*n = n^2
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
sum += arr[i][j];
}
}
return sum; // 1회
}n^2 + 2 → O(n^2)
O(2n)
기하급수적 복잡도(exponential complexity)라고 부르며, 빅오 표기법 중 가장 느린 시간 복잡도를 가진다.
가장 대표적인 것이 재귀로 구현하는 피보나치 수열이다.
function fibonacci(n) {
if (n <= 1) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}구현한 알고리즘의 시간 복잡도가 O(2n)이라면 다른 접근 방식을 고민해 보는 것이 좋다.
데이터 구조별 시간 복잡도
배열 정렬 알고리즘별 시간 복잡도
출처
