[시간복잡도] 별찍기 문제의 시간복잡도가 O(N^2)인 이유에 대하여

Development/Algorithm

by Developer, Jiyong Kim 2024. 7. 16. 15:33

알고리즘을 공부할 때마다 중요하다고 하는 것이 시간복잡도이다. 대충 이해한 것 같다고 생각해도, 막상 복잡도 계산해보라고 하면 못한다. 오늘은 어떻게든 시간복잡도를 파악해보려고 한다.

이해가 안되니 암기라도 해야지 하고 여러 문제를 들여다 보던 중 구현하기는 엄청 쉬운데 시간복잡도 계산은 이해가 되지 않는 문제를 마주쳤다. 바로 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)