점근표기법과 시간복잡도
#점근 표기법
어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법으로, 알고리즘의 복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰입니다.
점근 표기법에는 Big-O 표기법, 세타 표기법, 오메가 표기법이 있습니다.
접근 표기법의 특징으로는
- 가장 큼 영향력이 있는 항만 표시 ==> O(N^3 + N^2 + N) → O(N^3)
- 상수항은 무시 ==> O(2N+1) → O(N)
# Big-O표기법
점근표기법 중 가장 많이 쓰이는 빅오표기법에 대해 설명하겠습니다.
예를 들어,
| 0.1 | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 | 0.1 |
7개의 공간에서 앞 칸부터 순회하면서 원하는 데이터를 찾는다고 했을 때, 한 칸을 수행하는데에 소요되는 시간을 0.1초라고 하면, 최소 0.1초 최대 0.7초가 소요될수 있습니다.
이 때, 가장 상한 선인 0.7초를 시간복잡도로 표기하는 것이 Big-O 표기법입니다
빅오 표기법의 특징으로 괄호안의 복잡도연산의 크기는 보통 연산의 크기와 같다고 보시면 됩니다.
# 공간복잡도
데이터 관리에 필요한 공간으로 데이터 양의 변화에 따라 공간이 변화하며 그 예상 공간 소요를 측정합니다.
# 시간복잡도
데이터 처리에 소요되는 시간으로 데이터양의 변화에 따른 소요시간을 변화를 통해 예상 처리 시간을 측정합니다.
시간복잡도를 통해 지연 장애가 발생했을 때 발생 원인을 찾을 수 있는 근거가 됩니다.
# O(1)
O(1)은 입력 데이터의 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘 ( 배열의 random access , hash)
# O(N)
입력 데이터의 크기에 비례해서 시간이 소요되는 알고리즘
# O(N^2)
입력데이터의 제곱에 비례해서 시간이 소요되는 알고리즘
# O(logN)
이진탐색 알고리즘으로, 보통 한번 연산을 할떄마다 연산의 범위가 반씩 줄어드는 경우에 시간복잡도 O(logN)을 가집니다
up&down 게임을 생각하면 이해가 쉽습니다. 예를 들어,
| 1 | 3 | 4 | 6 | 7 | 9 | 11 |
우리가 찾고자하는 데이터가 9일때, 6을 기준으로 반으로 나눌수 있습니다.
| 7 | 9 | 11 |
나누고 남은 데이터를 또 반으로 나누는데, 우리가 찾고자하는 데이터가 9였으니 2번만에 데이터를 찾을 수 있게 된것이죠.
이렇게 O(logN)시간 복잡도를 가지는 알고리즘을 사용하면, 원래는 순차적으로 데이터를 찾는것보다 빠르게 찾을 수 있습니다.
# O(NlogN)
시간 복잡도 O(NlogN)을 가지는 대표적인 예는 merge sort입니다.
정렬하는 방법(quick sort, bubble sort, merge sort, ...)중 merge sort는 주어진 데이터 집합에서 절반씩 나누면서 데이터 분할을 하고(O(logN)), 하나씩 순차적으로 비교해가면서 정렬을 하게되는데, 이게 데이터 갯수 N번만큼의 과정을 거치기 때문에 NlogN이 됩니다.