알고리즘에 관해 공부를 하다보면 자연스럽게 접하게 되는 2가지 단어가 있다.
바로 시간 복잡도와 공간 복잡도이다.
지금까지 두루뭉실하게 알고 있던 2가지 개념에 대해 정리를 해보았다.
1. 시간 복잡도
시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 분석하는 방법이다.
알고리즘의 시간 복잡도는 연산의 횟수를 세고 처리해야 할 데이터의 수 n에 대한 연산 횟수의 함수T(n)을 만들어서 계산한다.
연산 횟수의 카운팅에는 3가지의 경우가 있다.
1. 최선의 경우 (Best Case)
2. 최악의 경우 (Worst Case)
3. 평균적인 경우 (Average Case)
알고리즘이 복잡해질수록 평균적 경우는 구하기 어려워지기에
최악의 경우를 계산하는 방식 Big O 표기법(Big O Notation)을 주로 사용하고
Big O 표기법의 예제는 다음과 같다
여기서 n은 입력되는 데이터를 의미한다.
O(1): 스택의 Push, Pop
O(log n) : 이진트리
O(n) : for문
O(n log n) : 퀵 정렬, 병합정렬, 힙 정렬
O(n2) : 이중 for문, 삽입정렬, 거품정렬, 선택정렬
O(2n) : 피보나치 수
2. 공간 복잡도
공간 복잡도는 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법이다.
공간 복잡도 역시 보통 최악의 경우(Worst Case)를 따져 Big O표기법으로 그 복잡도를 판단하게 된다.
하지만 공간 복잡도는 작성한 프로그램이 얼마나 많은 공간을 차지하느냐의 문제이다보니 컴퓨터의 성능이 좋아진 요즘에는 중요도가 떨어졌다고한다.
그러나 빅데이터를 처리하는 경우, 공간 복잡도가 커지가 된다면, 메모리에 프로그램이 한번에 올라가지 않아 프로그램을 실행할 수 없는 문제가 발생할 수 있다. 이렇기에 공간 복잡도 역시 신경써서 작성해야한다.
공간 복잡도를 결정하는것은 보통 배열의 크기가 몇인지, 얼마 만큼의 동적 할당인지, 몇 번의 호출을 하는 재귀 함수인지 등이 공간 복잡도에 영향을 끼친다.
마지막으로 다시 한번 정리하자면
시간 복잡도는 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 분석하는 방법
공간 복잡도는 작성한 프로그램이 얼마나 많은 공간(메모리)을 차지하느냐를 분석하는 방법이다.
