Namu | 나무 개발자 블로그입니다
시간/공간 복잡도와 Big-O 표기법 by namu
[목차]
[참조]
들어가며
어떤 알고리즘이 주어졌다고 했을 때, 그것을 어떻게 구현하는가 혹은 프로그래밍 언어의 문법을 어떻게 사용하는가 따라 성능 차이가 있을 수 있다. 이전보다 더 나아보이는 방식으로 코드를 개선하기는 했는데, 정확히 얼마만큼의 성능이 좋아졌을까? 이 글에서 알고리즘의 성능을 분석하는 방법을 알아보자.
시간 복잡도
1 ~ 100 의 합을 구하는 문제가 주어졌다고 하자.
처음에는 100번의 반복연산을 통해 값을 구하는 알고리즘을 구현했다.
하지만 ‘N * (N + 1) / 2’ 의 공식을 알게 된 이후 더 나은 방식으로 코드를 개선했다.
3번의 연산만 하면 동일한 결과가 나오기 때문에 효율성이 획기적으로 증대되었다고 생각된다.
하지만 오늘날의 컴퓨터 성능 면에서 3번의 연산이나 100번의 연산이나 실제 실행시간 면에서 사실상 큰 차이가 없다. 한 번의 연산이 수행되는 속도 자체는 하드웨어적인 성능에 따라 서로 다를 수 있기 때문에 우리는 그러한 연산이 몇번 수행되는지를 측정하여 성능을 비교한다. 만약 동일한 하드웨어 성능의 두 컴퓨터로 두 알고리즘의 성능을 비교한다고 하면, 연산이 몇번 수행되는지에 따라 총 시간이 결정되기 때문이다.
그러므로 시간 복잡도에서 시간은 입력 값 n에 따라 수행되는 연산의 횟수를 의미한다.
확실히 100번보다는 3번의 연산으로 동일한 결과를 출력하는 알고리즘이 시간 복잡도 면에서 더 효율적이라고 볼 수 있다.
시간 복잡도 : 입력 값 n에 따라 수행되는 연산의 횟수
시간 복잡도 측정의 목적은 실제 처리 시간을 재는 것이 아닌 데이터 증가량에 따른 처리 시간 증가비율을 예측하는 데 있다. 따라서 3번 혹은 100번의 연산 그 자체보다도, 데이터의 양이 점점 커진다는 가정 하에 해당 알고리즘이 수행됨에 있어서 얼마만큼의 비율로 처리 시간이 증가하는지 알아내는 것이 핵심이다.
공간 복잡도
공간 복잡도는 보다 물리적인 측면에서 계산된다.
시간 복잡도가 알고리즘 수행에 시간이 얼마만큼 걸리는지를 나타낸 것이라면,
공간 복잡도는 알고리즘 수행에 얼마만큼의 저장 공간(메모리, 디스크)이 필요한지를 나타낸 것이다.
예를 들어 알고리즘 A 는 수행에 1MB 메모리가 필요하고 알고리즘 B 는 1KB 메모리가 필요하다면, B 는 A 에 비해 1,024배 효율적인 알고리즘이다.
그러나 대부분의 프로그램 환경에서 공간에 대한 비용보다 시간에 대한 비용이 더 많이 들고, 그 증가율도 크기 때문에 특수한 몇몇 경우를 제외하고 알고리즘 성능 분석이라 함은 시간 복잡도를 의미한다.
성능 분석하기
1 ~ 100 의 합을 구하는 두 알고리즘에 대한 시간 복잡도를 다음처럼 수행되는 연산의 빈도수로 나타낼 수 있다.
| 알고리즘 (a) | 알고리즘 (b) |
|---|---|
| CalcSum( n ) { | CalcSum( n ) { |
| i <- start; | count <- n; |
| sum <- 0; | sum <- 1 + n; |
| sum <- sum * count; | |
| for ( ; i <= n; i <- i + 1) { | sum <- sum / 2; |
| sum <- sum + i; | return sum; |
| } | } |
| return sum; | |
| } |
- 알고리즘 (a) 의 연산 빈도수: 2 + n x 3 = 3n + 2
- 알고리즘 (b) 의 연산 빈도수: 4
위 두 알고리즘을 시간 복잡도 함수로 나타낸 것이다.
시간 복잡도 함수는 입력값 n에 따라 연산 수행 횟수가 어떻게 결정되는지 함수로 나타낸 것이다.
Drop constants
일반적으로 시간 복잡도를 나타낼 때는, n의 값이 무한히 커지는 상황을 가정하여 무의미한 계수 및 상수를 제외(Drop constants)한다. 이는 앞서 언급했듯이 실제 처리 시간이 아닌 데이터 증가에 따른 처리 시간 증가 비율을 알아내는 것이 목적이기 때문이다. 따라서 (a) 에서는 계수 3과 상수 2를 제외한 ‘n’으로 나타내고, (b) 에서는 상수의 기본 단위인 ‘1’로 나타낸다.
- 알고리즘 (a) 의 시간 복잡도 함수 표현: n
- 알고리즘 (b) 의 시간 복잡도 함수 표현: 1
Big-O 표기법
알고리즘의 시간 복잡도는 시간 복잡도 함수 중에서 가장 큰 영향을 주는 n에 대한 항만 표현한다. 이를 위해 빅-오 표기법(Big-Oh notation)을 사용한다. 만약 n차 항이 여러 개 존재한다면, 그중 가장 큰 차수의 n만 표현한다.
위 알고리즘 (a) 의 빅-오 표기법은 O(n) ‘빅-오 오브 엔’, 알고리즘 (b) 의 빅-오 표기법은 O(1) ‘빅-오 오브 원’이다.
빅-오 표기법의 정의
두 개의 함수 f(n) 과 g(n) 이 주어졌을 때, 모든 n >= n0 에 대해 | f(n) | <= c | g(n) | 을 만족하는 2개의 상수 c 와 n0 가 존재하면 f(n) = O(g(n)) 이다.
다음은 시간 복잡도에서 많이 사용하는 최고차항들을 정리한 것이다.
- O(1) : 상수
- n에 상관 없이 항상 일정한 시간이 소요된다
- O(logn) : 로그
- 데이터가 10의 n승 만큼 커지면 처리 시간은 n배 만큼 커진다
- 즉, 데이터 증가량에 따라 지수 함수의 역함수씩 처리 시간이 증가한다고 생각하면 된다
- 대표적으로 이진 탐색이 있는데, 연산이 진행됨에 따라 전체 데이터 수의 절반씩 그 범위가 줄어든다
- 선형 함수보다 처리 속도가 빠른 특징이 있다
- O(n) : 1차, 선형
- 데이터가 커지는 만큼 처리 시간 커진다. 대표적으로 liner 탐색 알고리즘이 있다
- O(nlogn) : 선형 로그
- 선형 함수로 100배만큼 처리 시간이 커졌을 때, 로그 배수인 2배만큼 더 커진다(200배, 1000배면 3000배)
- 여기서 로그 배수 2는 10²의 역함수인 log10²의 결과이다
- O(n²) : 2차
- 산술급수적으로 증가한다
- 대표적으로 이중 루프(10개씩 10번, 100개씩 100번)가 있다
- O(nm), O(n³) 는 정도의 차이만 있지 이와 비슷한 양상을 보인다
- O(2ⁿ) : 지수(exponential)
- 기하급수적으로 증가한다
- 피보나치 수열이 기하급수적 황금비율의 대표적인 예이다
- O(n!) : 계승(factorial)
이들의 대소 비교는 다음과 같다.
- O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(2ⁿ) < O(n!)
이미지 출처: velog.io