이것보다 더 효율적인 방법은 없을까 , 이게 제일 좋은 방법이 맞나
효율적인 방법을 고민한다는것은 시간 복잡도를 고민한다는 것과 같다.
이번에는 시간 복잡도와 Big-O 표기법에 대해서 다뤄보겠습니다.
시간 복잡도
알고리즘에 대한 로직을 작성할 때 , 시간복잡도를 고려한다는 것은 무슨 의미인가?
입력값의 증가/감소함에 따라 시간이 얼마만큼 비례하여 증가/감소 하는가?
Big-O표기법
시간 복잡도를 표기하는 방법 중엔
- Big-O
- Big-Ω
- Big-θ
등이 있는데, 각각 최악,최선,중간(평균)의 경우 입력값의 증가에 따라 시간복잡도가 얼마나 증가하는지 표기하는 방법이다.
이중 가장흔히 사용되는것이 Big-O 표기법이다.
이유는?
" 최소한 이 시간 이상 걸린다" 혹은 "이정도 시간이 걸린다" 를 고려하는것은 나이브하다.
"이정도 시간까지 걸릴 수 있다" 를 고려해야 그에 맞는 대응이 가능하다.
O(1)
Big-O 표기법은 입력값의 증가/감소함에 따라 시간이 얼마만큼 비례하여 증가/감소 하는가를 표기하는 방법이라 언급했다.
O(1)는 constant complexity라고 부르며, 입력값이 증가해도 시간은 늘어나지 않음을 의미한다. 달리말하면 입력값이 얼마나 커지는지와 관계없이, 즉시 출력값을 얻어낼 수 있다는 의미이다.
O(1)의 시간복잡도를 가진 알고리즘을 살펴보겠다.
function 0_1_alogrithm(arr,index){
return arr[index];
}
let arr=[1,2,3,4,5];
let index = 1;
let result = 0_1_algorithm(arr,index);
console.log(result);//2해당알고리즘은 입력값의 크기랑 관계없이 바로 값을 얻을수있다.
O(n)
O(n)은 linear complexity라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.
예를 들어 입력값이 1일때 1초의 시간이 걸리고, 입력값을 100배로했을때, 100배인 100초가 걸리는 알고리즘을 구현했다면 그 알고리즘은 O(n)의 시간복잡도를 가진다고 할 수 있다.
O(n)의 시간 복잡도를 가진 알고리즘을 한번 살펴보겠다.
function 0_n_algorithm(n){
for(let i =0; i<n;i++){
//do something for 1sec
}
}
function another_0_n_algorithm(n){
for(let i=0; i<2n;i++){
//do something for 1sec
}
}
같은비율로 증가하는 O(n)이고
두번째함수는 코드는 O(2n)인것 처럼보이지만,
사실 이또한 O(n)으로 표기한다.
입력값이 커질수록 계수(n앞의 수)는 의미를 점점 퇴색하기 때문에
쉽게생각하면 뒤에 무한대의 수가 온다면 앞에서 몇배를 해주던 무한대이다.
그러므로 뒤에 무수히 큰수가 온다면 앞의 보이는 작은 수는 무시할수있다.
O(log n)
O(log n)은 logarithmic complexity라고 부르며 Big-O표기법중 O(1)다음으로 빠른 시간 복잡도를 가진다.
자료구조에서 다루던 BST (바이너리 서치 트리)
BST에선 원하는 값을 탐색할때 노드를 이동할때마다 경우의 수가 절반으로 줄어든다, 이해하기 쉬운 게임으로 비유해보자면 up&down게임을 예로 들을수있다.
매번 숫자를 제시할때마다 경우의 수가 절반이 줄어들기 때문에 최악의 경우에도 원하는 숫자를 찾아낼수있다.
(이분탐색)
O(n²)
O(n²)은 quadratic complexity라고 부르며, 입력값이 증가함에 따라 시간이 그의 제곱수의 비율로 증가하는 것을 의미한다.
예를 들어 입력값이 1일 경우 1초가 걸리던 알고리즘에 5라는 값을 주었더니 25초가 걸리게 된다면 이 알고리즘의 시간 복잡도는 O(n²)라고 할수 있다.
O(n²)의 시간복잡도를 가진 알고리즘은 아래와 같다 (예시)
function 0_quadratic_algorithm(n){
for(let i =0; i<n; i++){
for(let j=0;j<n; j++){
// do somthing for 1sec
}
}
}
function another_0_quadratic_algorithm(n){
for(let i =0; i<n; i++){
for(let j=0; j<n; j++){
for(let k=0; k<n; k++){
// do something for 1sec
}
}
}
}
2n, 5n 을 모두 O(n)이라고 표현했던것과 같은 맥락으로 n³ n⁵도 모두 Big-O표기법으로는 O(n²)라고 표기한다.
O(2ⁿ)
O(2ⁿ)은 exponential complexity라고 부르며 Big-O표기법중 가장 느린 시간 복잡도를 가진다.
종기 42번 접으면 그 두께가 지구에서 달까지의 거리보다 커진다는 이야기를 들어본적이있다.
고작 42번만에 얆은 종이가 그만한 두께를 가질수 있는것은 매번 접힐때마다 두께가 2배로 늘어나기 때문이다.
구현한 알고리즘의 시간 복잡도가 O(2ⁿ)이라면 다른 접근방식을 고민해보자.
function fibonacci(n){
if(n<=1){
return 1;
}
return fibonacci(n-1) + fibonacci(n-2);
}
재귀를 구현하는 피보나치 수열이 대표적인 O(2ⁿ)시간 복잡도를 가진 알고리즘이다.
브라우적 개발자 창에서 n을 40으로 두어도 수초가 거리는것을 볼수있고
n이 100이상만 되어도 평생 결과를 반환받지 못할것이다.
일반적으로 코테에서는 정확한 값을 제한 시간내에 반환하는 프로그램을 작성해야하는데
컴파일러 혹은 컴퓨터 의사양에 따라 차이는 있겟지만 시간제한과 주어진 데이터 크기 제한에 따른 시간 복잡도를 어림으로라도 예측해보는것이 중요하다.
예를 들어 n만큼의 크기를 가지는 데이터가 있고, n의 제한을 1,000,000보다 작은 수라고 했을때, 예상되는 시간 복잡도는 O(n) 혹은 O(nlogn)을 예측하여 프로그램을 작성할수 있다.
왜 n²의 시간 복잡도는 예측할수 없느냐고 했을때 실제 수를 대입해보면 어느정도 답이 나온다.
1,000,000의 ²정도만 되어도 즉시 처리하기에는 무리가 있는 숫자가 나오게됩니다.
반대의 경우로 n≦500정도로 제한되었을때 n³정도까지는 예측할수 있다 n³으로 문제를풀게 된다면 금방 풀 수 있을텐데, 시간복잡도를 log n까지 낮추느라 끙끙댈 필요가없다는 말로도 바꿀수있다.
| 데이터 크기 제한 | 예상되는 시간 복잡도 |
|---|---|
| n ≤ 1,000,00 | O(n) or O (logn) |
| n ≤ 10,000 | O(n²) |
| n ≤ 500 | O(n³) |
