시간 복잡도와 공간 복잡도

서론

백준으로 알고리즘을 풀다보면 단순히 출력값을 구현해야하는 것이 아닌, 복잡도를 이해하면서 효율적으로 문제를 풀어야 하는 순간들을 맞이했다.

이러한 이유로 인해 이번 기회에 시간 복잡도와 공간 복잡도가 무엇인지 이해해보는 시간을 가지도록 하겠다.

 

# 복잡도란

 

복잡도는 알고리즘의 성능, 효율성을 나타내는 척도이다.

각 알고리즘이 주어진 특정 크기의 입력(n)을 기준으로 수행시간(연산) 혹은 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준을 제시한다.

 

1. 시간 복잡도 (Time Complexity)

시간 복잡도란 특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수를 나타낸다.

이름이 시간 복잡도인 것과는 별개로 연산의 횟수를 세는 이유는 다음과 같다.

1. 모든 OS, IDE, 플랫폼에서 동일한 결과가 나오지 않는다.

2. 실행시간 측정을 위한 또다른 방법이 필요하다.

알고리즘의 성능 평가는 최선의 경우, 최악의 경우, 평균의 경우로 나눠진다. 이들 중 알고리즘 분석 시 평균의 경우와 최악의 경우가 가장 많이 활용되며, 알고리즘이 복잡해질수록 평균을 구하기 어려워져 최악의 경우로 알고리즘 성능을 파악한다.

평소의 경우	최악의 경우, 평균의 경우
복잡한 알고리즘의 경우	최악의 경우

 

2. 공간 복잡도 (Space Complexity)

공간 복잡도란 프로그램 실행과 완료에 얼마나 많은 공간(메모리)가 필요한지를 나타낸다.

알고리즘을 실행시키기 위해 필요한 공간(space)는 고정 공간과 가변공간, 2가지로 나눌 수 있는데

1. 알고리즘과 무관한 공간, 즉 고정 공간

-> 코드가 저장되는 공간으로, 알고리즘 실행을 위해 시스템이 필요로 하는 공간을 말한다.

2. 알고리즘과 밀접한 공간, 즉 가변 공간

문제를 해결하기 위해 알고리즘이 필요로 하는 공간, 변수를 저장하는 공간, 순환 프로그램일 경우 순환 스택(recursion stack) 등

 

즉, 시간 복잡도는 얼마나 빠르게 실행되는지, 공간 복잡도는 얼마나 많은 자원(메모리 공간)이 필요한지를 판단한다.

시간 복잡도와 공간 복잡도는 반비례하는 경향이 있어, 보통 알고리즘의 성능을 판단할 때는 시간 복잡도를 위주로 판단한다.

 

# 빅오 표기법 (Big-O notation)

빅오 표기법은 복잡도를 나타내는 점근 표기법 중 가장 많이 사용되는 표기법이다.

빅오 표기법이 가장 많이 사용되는 이유는 알고리즘 효율성을 상한선 기준으로 표기하기 때문이다.

즉, 최악의 경우를 고려하는 데 가장 좋은 표기법이다! (앞서 작성했듯이, 알고리즘이 복잡해질수록, 최악의 경우는 더욱 빛을 발한다.)

+) 빅오메가는 하한선을 기준으로, 빅세타는 상한선과 하한선 사이를 기준으로 표기한다.

 

# 빅오 표기법의 수학적 정의

빅오 표기법의 수학적 정의는 다음과 같다.

O(g(n)) = {f(n) : there exist positive constants c and $ n_0 $ such that 0≤f(n)≤cg(n) for all n≥$ n_0 $}

n0를 기준으로 n0보다 오른쪽에 있는 모든 n 값에 대해 함수 f(n)은 함수 cg(n)보다 같거나 작다는 의미이다.

- 점근적 상한선

즉 빅오 표기법에서는 주어진 알고리즘이 아무리 나빠도 비교하는 함수와 같거나 좋다!
그래프가 아래에 있을수록 수행시간이 짧으므로 성능이 좋은 것이다.

+) 빅오 표기법의 대표적인 2가지 특징으로는 상수항을 무시하는 것(O(2n)은 O(n)으로 간주)과 영향력이 없는 항을 무시하는 것이 있다(O(n^2+2n+1)은 O(n^2)으로 간주).

 

# 시간 복잡도와 빅오 표기법

시간 복잡도란 앞서 말했듯 특정 크기의 입력(n)을 기준으로 실행하는 연산의 횟수이다.

하지만 알고리즘이 실행될 때 연산되는 모든 횟수를 세는 것이 아니라 알고리즘에서 핵심이 되는 연산의 횟수만 세어주면 된다.(빅오의 특징 2가지)

* 복잡도소요 시간예시

O(1)	상수 시간	스택에서 Push, Pop
O(log n)	로그 시간	이진 트리
O(n)	직선적 시간	for 문
O(n log n)	선형 로그 시간	퀵 정렬(quick sort), 병합 정렬(merge sort), 힙 정렬(heap sort)
O(n^2)	2차 시간	이중 for 문, 삽입 정렬(insertion sort), 거품 정렬(bubble sort), 선택 정렬(selection sort)
O(C^n)	지수 시간	피보나치 수열

왼쪽에서 오른쪽으로 갈수록 성능이 떨어지며, 시간 복잡도가 좋지 않은 알고리즘이다.

 

# 공간 복잡도와 빅오 표기법

공간 복잡도는 앞서 말했듯 알고리즘 실행에 메모리가 얼마나 사용되는지를 계산하면 된다.

예를 들어 크기가 n인 array를 입력으로 주었을 때, 알고리즘이 n*n의 이차원 배열을 생성한다면 이 알고리즘의 공간 복잡도는 n^2이 된다.

알고리즘의 공간 복잡도를 계산한 후 빅오 표기법의 특징 2가지(상수항과 영향력이 없는 항 제거)를 고려해 나타내면 빅오 표기법이 된다.

 

공간 복잡도는 보통 중요하게 생각하지 않는 경우가 많지만 많은 데이터를 다루는 경우 공간 복잡도가 커지게 되면 프로그램이 메모리에 올라가지 않아 실행할 수 없게 될 수도 있기에 알고리즘 작성 시 공간 복잡도도 어느 정도 신경써서 작성하는 것이 좋다.

 

# Big-O 표기법으로 나타낸 자료구조별 시간 복잡도

 

# Big-O 표기법으로 나타낸 정렬 알고리즘 별 복잡도

 

 

# 참고한 사이트

https://velog.io/@welloff_jj/Complexity-and-Big-O-notation

복잡도(Complexity): 시간 복잡도와 공간 복잡도, 그리고 빅오(Big-O) 표기법