시간복잡도와 공간복잡도, Big O 표기법
개요
개발자로써 취업을 하는 과정에서 다양한 회사들이 코딩테스트를 보는 경우가 많습니다.
코딩테스트는 알고리즘과 자료구조에 많이 관련이 되있는데, 취업시의 코딩 테스트를 제외하고서도
시간 복잡도를 이해해야 하는 이유는 알고리즘을 빠르게 분석 및 상황에 맞춰 써야 할 알고리즘을 파악, 자신의 코드를 평가 할 수 있기 때문에 시간 복잡도를 이해를 해야합니다.
요약하자면, 효율적인 코딩을 하려면 자료구조와 알고리즘을 필수적으로 잘 다뤄야 한다고 볼 수 있습니다.
그러기 위해서 알고리즘의 최적화된 사용법을 알아야하는데, 그중 시간복잡도와 공간복잡도에 대해 알아보려고 합니다.
1. 시간 복잡도
입력 크기에 대해 어떠한 알고리즘이 실행되는데 걸리는 시간이며, 주요 로직의 반복횟수를 중점으로 측정된다.
시간복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미하며, 알고리즘을 위해 필요한
연산의 횟수 또한 의미합니다.
※ 시간 복잡도의 빠르다, 느리다 라는 시간적인 의미를 두지 않는 이유는 각각의 하드웨어마다 차이가 있는점과
같은 하드웨어 더라도 사용중인 메모리의 상태에 따라 시간값이 달라지기 때문입니다.
2. 공간 복잡도
입력크기에 대해 어떠한 알고리즘이 실행되는데 필요한 메모리의 양을 의미합니다.
예시로는 변수를 선언 또는 요소들을 담을 공간(자료구조)들이 전부 메모리에 들어가는데, 이것을 공간 복잡도라고 할 수 있습니다.
3. 시간 복잡도와 공간 복잡도의 연관 관계
시간 복잡도는 알고리즘에서 입력 크기에 따라 알고리즘의 실행시 걸리는 연산의 횟수를 의미하며,
공간 복잡도는 입력 크기에 대해 알고리즘의 실행시 필요한 메모리 양을 의미합니다.
일반적으로 메모리 연산 횟수를 줄이기 위해(시간 복잡도)서 더 많은 메모리 공간(공간 복잡도)을 사용 하거나,
반대로 메모리 사용을 최소화 하기위해 메모리 연산이 증가하는 경향이 있습니다.
두 복잡도는 알고리즘의 다양한 요인에 의해 영향을 받을 수있으며, 한 측면이 향상되면 한 측면이 저하될 수 있습니다.
이것을 트레이드 오프 (Trade-off)관계라고 합니다.
결론적으로, 시간 복잡도와 공간 복잡도는 알고리즘의 성능에 대해 각각 연산횟수, 메모리 사용량을 나타낼 수 있으며
상황에 따라 시간 복잡도와 공간 복잡도의 우선도를 고려하거나, 시간 복잡도와 공간 복잡도를 동시에 고려 해야합니다.
4. Big O 표기법
빅오(Big-O) 표기법은 시공간 복잡도를 수학적으로 표시하는 표기법중 가장 대표적인 방법입니다.
빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간을 고려할 수 있습니다.
표기법의 방식은 가장 빠르게 증가하는 항만을 고려하는 방식이며, 인풋 데이터 증가율에 따른 알고리즘 성능을
논리적으로 예측하기 위해 사용합니다.
- 가장 빠르게 증가하는 항만을 고려한다. 즉, 가장 높은 차수만 남기는 방식을 취한다.
- 빅오는 점근선의 상한 범위를 찾는 것이다.
- 작은 N이나 상수 인자는 고려하지 않는다.
- 빅오 표기법에서 n이란 입력되는 데이터 (Data Input)을 나타냅니다.
시간 복잡도 성능 비교에 따라
O(1) < O(㏒ N) < O(N) < O(N ㏒ N) < O(N²) < O(2ⁿ)
상수 함수 < 로그 함수 < 선형 함수 < 다향 함수 < 지수 함수
순이며, 오른쪽으로 갈수록 효율이 떨어집니다.
Big-O 표기법의 종류와 예제
1. O(1) - 상수
입력 데이터의 크기에 상관없이 동일한 수의 연산이 필요하며 즉시 출력값을 얻어낼 수 있는것을 의미합니다.
대표적으로는 자료구조 Stack의 Push, Pop이 있습니다.
Stack, Queue
해당 이미지는 각각 Stack과 Queue의 내부 구조입니다.
Stack을 예시로 할 경우 pop함수를 사용하여 저장해둔 값을 꺼내오는데, 이때 pop의 특성은 Stack의 가장 마지막에 들어온 데이터를리턴하며, 삭제하는 구조로 가장 최상위 데이터 하나를 제외한 다른 탐색은 하지않고 즉시 출력값을 얻어낼 수 있습니다.
2. O(log N) - 로그
입력 데이터의 크기가 커질수록 처리 시간이 log만큼 짧아지는 경우에 log 시간을 표현합니다. 대표적인 예시로 BST(Binary Search Tree)가 있으며, 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하기때문에 데이터 개수가 절반씩 줄어든 다는 점, 2배로 늘어나도 나뉘는 수가 1개 더 늘어날 뿐인 점에서 O(log N)이라 표현할 수 있습니다.
이진탐색트리 (BST)
해당 이미지는 이진탐색트리의 예시이며, 탐색하려는 값을 왼쪽에 있는 Branch 부터 비교, 탐색하는 형태로 이루어져 있는 자료구조입니다. BST는 하나의 branch로 치우쳐진 경우 O(n)을 될 수 있지만, 일반적으로는 트리의 높이 h에 따른 최대 노드의 수는 2^h - 1의 개수를 가질 수 있으며, 이로인해 O(log N)이라 표현할 수 있습니다.
3. O(N) - 선형
입력값이 증가함에 따라 시간또한 비례해서 증가합니다.
대표적인 예시로 조건의 값이 참이 될때까지 증감연산을 하는 for문이 있습니다.
4. O(N log N) - 선형 로그
입력 데이터가 많아질수록 처리 시간이 로그 배만큼 늘어납니다.
대표적인 예시로 퀵 정렬(Quick Sort), 병합정렬(Merge Sort), 힙 정렬(Heap Sort)가 있습니다.
병합정렬의 예시
병합정렬 시간복잡도 예시
병합정렬 (Merge Sort)의 경우 List,Array 등의 저장된 값을 절반씩 나누어 번호순, 사전순과 같이 정해진 순서대로 정렬하는 알고리즘입니다.
정렬된 두 집합을 하나의 정렬된 집합으로 합치는데에 필요한 시간복잡도가 O( 두 집합의 원수의 개수),
그리고 분할 정복을 이용하여 병합정렬을 구현하면 총 시간복잡도가 O(N log N)입니다.
5. O(N²) - 다항
2차 복잡도 라고 부르기도하며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비례하여 증가하는 것을 의미합니다.
대표적인 예시로는 루프 안에서의 루프를 실행하는 이중 for 문이 있습니다.
6. O(2ⁿ) - 지수
기하급수적 복잡도 라고 불리기도하며, Big-O 표기법중 가장 느린 시간 복잡도를 가지고 있습니다.
데이터의 양이 많아질수록 처리시간이 기하급수적으로 증가합니다.
대표적인 예시로는 피보나치 수열이 있습니다.
정리
시간 복잡도는 메모리가 실행되는데 걸리는 시간이 아닌, 메모리의 연산 횟수를 의미한다.
공간 복잡도는 메모리의 사용량을 의미한다.
시간 복잡도와 공간 복잡도는 서로 반비례 형태로 이루어져 있으며,알고리즘의 성능을 최적화 하기위해
두 복잡도를 고려해야한다.
복잡도의 표기법에는 대표적으로 최악의 상황을 고려하는 빅오 (Big-O)표기법이 있으며
사용하는 데이터의 개수와 소모되는 시간에 따라 미분, 적분형식의 그래프 형태를 나타내기도한다.
출처 및 참고 자료