알고리즘의 시간복잡도, 공간복잡도란? (feat. Big O Notation)

Big O 표기법 (Notation) 이란?

• Big O 표기법이란 알고리즘의 컴퓨터적인 복잡도를 기술하는 방식이다.
• 시간 복잡도 와 공간 복잡도 로 나뉘게 된다.
• 시간 복잡도: 입력값이 늘어남에 따라 얼마나 실행 시간이 늘어나냐를 의미한다.
• 공간 복잡도: 입력값이 늘어남에 따라 얼마나 메모리 공간을 많이 차지하냐를 의미한다.

일반적으로 알고리즘 문제는 더 나은 공간 복잡도보단 더 나은 시간 복잡도를 요구한다.

실제 표기 예제

• O(n)
• O(n²)
• O(2ⁿ)
• O(log n)
• O(n * m)

여기서 n 은 보통 입력으로 들어온 배열의 길이거나 문자열의 길이이다.

Big O 표기법에서 상수는 무시된다

ex) O(2n) 이 있다면, O(n) 으로 표기하는 것과 같다.

위에서 시간 복잡도와 공간 복잡도 모두 '입력값이 늘어남에 따라' 라는 조건이 붙었던 것을 기억해보면 쉽다. 상수는 입력 값이 커질수록 그 의미가 퇴색되어 '복잡도' 에 포함되지 않는다. 복잡도를 계산할 때는 n 이 무한대로 향한다고 생각하기 때문에, 상수는 의미가 없어지는 것이다.

Big O 에 n 이 여러번 등장하는 경우 가장 큰 n 하나만 남긴다

예를 들어, O(2ⁿ + n² - n) 이라는 표기가 있다면, O(2ⁿ) 만 남겨도 무관하다. 그 이유는 위에서 상술했듯, n 이 무한대로 간다는 방향성 아래에 복잡도를 계산하기 때문이다.

가장 이상적인 시간 복잡도는 O(1) 이다

상수 시간 혹은 상수 공간이라고 불린다. 이 말은 즉, 항상 같은 양의 리소스를 사용한다는 뜻이다.

복잡도는 보통 최악의 시나리오를 가정한다

복잡도를 구할 때는 보통 3가지 경우를 구한다.

• 최적(Best) 케이스
• 평균 케이스
• 최악(Worst) 케이스

알고리즘 문제를 풀 때, 우리가 관심있는 복잡도는 최악 케이스의 복잡도이다.

복잡도를 구하는 이유

알고리즘을 분석하고 어떤 부분을 개선해나갈 수 있는지 알아내기 위함이다.

실제로 복잡도 구해보기

단순 for 문

for (let i = 0; i <= n; i++) {
  // do something
}

• n 번의 반복동안 작업을 수행하기 때문에 O(n) 이다.

2중 for 문

for (let i = 0; i <= n; i++) {
  for (let j = 0; j <= 100_000; j++) {
    // do something
  }
}

• O(100000n) 의 복잡도를 갖는다.
• 상수는 무시된다고 하였으므로, O(n) 과 동일하다.

실무와의 갭: O(n) 과 O(100000n) 의 복잡도는 동일하지만, 실무에서는 이러한 시간복잡도를 갖는 알고리즘이 있을 때, O(100000n) 이 훨씬 느리게 동작할 가능성이 크다. 복잡도는 이론상의 복잡도를 구하는 것일 뿐이다.

2중 for 문 2

for (let i = 0; i <= n; i++) {
  for (let j = 0; j <= m; j++) {
    // do something
  }
}

• 하나는 n 하나는 m 까지 반복하므로 O(n * m) 의 시간 복잡도를 갖는다.

2중 for 문 3

for (let i = 0; i <= n; i++) {
  for (let j = 0; j <= n; j++) {
    // do something
  }
}

• 두 개 다 n 까지 반복하므로 이제서야 O(n²) 의 시간 복잡도를 갖는다.

1중 for 문 2 개

for (let i = 0; i <= n; i++) {
  // do something
}

for (let j = 0; j <= m; j++) {
  // do something
}

• O(n + m) 의 시간 복잡도를 갖는다.

로그 시간에 대해

위의 for 문 예제에는 없었지만 O(log n) 과 같은 복잡도도 있다. 어떤 알고리즘이 O(log n) 의 시간 복잡도를 갖는다면, 이는 매우 빠른 시간 내에 실행된다. 지수함수 그래프와 반대라는 것을 생각해보면 쉽다.

O(log n) 에서 로그의 밑은 2 이다.

시간 복잡도에 log 가 등장한다는 것은 매우 많은 입력 값이 들어올 때마다 어디선가 고려할 사항들이 줄어드는 것이다. 이를테면 이진 탐색과 같은 경우가 있다.

계속 n / 2 의 요소만 고려하면 되기 때문에, O(log n) 의 시간복잡도가 나온다. 매 단계마다 고려할 입력이 50% 씩 줄어든다.

공간 복잡도 계산하기

for (let i = 0; i <= n; i++) {
  console.log(i);
}

위 코드의 공간 복잡도는 O(1) 이다. 변수를 저장하지 않기 때문이다.

for (let i = 0; i <= n; i++) {
  a[i] = i;
}

위 코드의 공간 복잡도는 O(n) 이다. 변수를 저장하고 있다.

for (let i = 0; i <= n; i++) {
  for (let j = 0; j <= n; j++) {
    a[i][j] = i * j;
  }
}

위 코드의 공간 복잡도는 O(n²) 이다.

'공간 복잡도는 얼마만큼의 공간에 값을 저장하냐' 로 쉽게 구할 수 있다.