알고리즘을 공부할 때마다 중요하다고 하는 것이 시간복잡도이다. 대충 이해한 것 같다고 생각해도, 막상 복잡도 계산해보라고 하면 못한다. 오늘은 어떻게든 시간복잡도를 파악해보려고 한다.
이해가 안되니 암기라도 해야지 하고 여러 문제를 들여다 보던 중 구현하기는 엄청 쉬운데 시간복잡도 계산은 이해가 되지 않는 문제를 마주쳤다. 바로 N개의 줄에 별을 찍어 출력하는 별찍기 문제.
// 입력 예제
5
// 출력 예제
*
**
***
****
*****
// 구현 예제
function makestars(n) {
for (let i = 1; i <= n; i++) {
const stars = '*'.repeat(i);
console.log(stars);
}
}
makestars(5);
지금까지 이해한 바로는 반복문을 한 번 쓰면 O(N), 두 번쓰면 O(N^2) 이런 식이었기 때문에, 코드만 놓고 보면 별찍기는 O(N^2)이 맞지만(for 안에 repeat으로 이중 반복) 수학적으로 생각했을 때 1+2+3+...+N이 N(N+1)/2가 되는 부분이 이해가 되지 않았다. 숫자를 하나씩 더하는 작업이기 때문에 N번 반복하는거니까 당연히 O(N)이라고 생각했다.
시간복잡도를 계산하고나서 코드를 작성해야하기 때문에 코딩을 하고나서 시간복잡도를 파악하는 것은 의미가 없다. 사실 1부터 N까지의 합 공식은 오래 전에 배웠었다. 공식만 주입식으로 외웠어서 기억이 안났나. 하여튼 단계별로 계산하면서 보니까 굉장히 흥미롭다.
1. 1부터 N까지의 합 정의
S = 1 + 2 + 3 + ... + N
2. 합을 뒤집어서 더하기
S = N + (N−1) + (N−2) + ... + 1
3. 두 식을 더하기
2S = (1+N) + (2+(N−1)) + (3+(N−2)) + ... + (N+1)
4. 간소화 하기: 각 쌍의 합은 N+1로 동일함
2S = (N+1) + (N+1) + (N+1) + ... + (N+1)
2S = N × (N+1)
5. S값 구하기
S = N(N+1)/2
시간복잡도는 최고차항을 남기고 계수를 지우는 방식으로 표현하기 때문에 1부터 N까지의 합을 구하는 알고리즘의 시간복잡도는 O(N^2)가 되는 것이다.
시간복잡도를 공부하면서 파악한 몇 가지 규칙과 패턴이 있다. 정리해두고 두고두고 써먹어야지.
입력 값(최대 연산 횟수) | 시간복잡도 |
n <= 10 | O(N!) |
n <= 25 | O(2^N) |
n <= 300 | O(N^3) |
n <= 5,000 | O(N^2) |
n <= 100만 | O(NlogN) |
n <= 2,000만 | O(N) |
n <= 10억 | O(logN) |
컴퓨터가 초당 연산할 수 있는 보수적 기준인 1,000~3,000만을 기준으로 계산.(최대 성능은 초당 1억 번)