복잡도에 대해서
1. 크게 시간 복잡도(Time Complexity)와 공간 복잡도로 나눌 수 있다.
2. 알고리즘의 성능 평가 및 효율성을 나타내는 척도이다.
3. 동일한 기능을 수행하는 알고리즘이 있을때 복잡도가 낮을수록 좋은 알고리즘이라 말한다.
1. 시간 복잡도
- 시간 복잡도(Time Complexity)는 알고리즘이 실행되는 동안 수행하는 기본적인 연산 횟수의 총량을 나타내며, 입력 크기에 대한 함수로 표현됩니다. 즉, 입력 크기가 증가함에 따라 알고리즘이 실행되는 데 걸리는 시간의 증가량을 나타내는 것입니다.
시간 복잡도를 표기하는 방법
- Big-O(빅-오) ⇒ 상한 점근
- Big-Ω(빅-오메가) ⇒ 하한 점근
- Big-θ(빅-세타) ⇒ 그 둘의 평균
- 위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다.
가장 자주 사용되는 표기법
- 빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다.
- “최소한 특정 시간 이상이 걸린다” 혹은 “이 정도 시간이 걸린다”를 고려하는 것보다 “이 정도 시간까지 걸릴 수 있다”를 고려해야 그에 맞는 대응이 가능하다.
2. 공간 복잡도
- 공간 복잡도(Space Complexity)는 알고리즘이 실행되는 동안 필요한 추가 메모리의 양을 나타냅니다. 즉, 입력 크기와 상관없이 알고리즘이 필요로 하는 메모리의 양을 나타내는 것입니다.
- 공간 복잡도 계산은 알고리즘에서 실제 사용되는 저장 공간을 계산하면 된다.
공간 복잡도 예시 - 1
- n! 팩토리얼 구하기
- n! = 1 x 2 x ... x n
- 구현 : 반복문
- n의 값에 상관없이 변수 n, 변수 fac, 변수 index 만 필요함
- 공간 복잡도는 O(1)
공간 복잡도 예시 - 2
- n! 팩토리얼 구하기
- n! = 1 x 2 x ... x n
- 구현 : 재귀함수
- 재귀함수를 사용하였으므로, n에 따라, 변수 n이 n개가 만들어지게 됨
- factorial 함수를 재귀 함수로 1까지 호출하였을 경우, n부터 1까지 스택에 쌓이게 됨
- 공간 복잡도는 O(n)
3. 빅오(Big-O) 표기법
- 빅오 표기법이란 알고리즘의 최악의 경우 복잡도를 측정하여 나타낸 것입니다.
- 빅오표기법에서 n은 입력되는 데이터의 개수를 나타낸다.
- 그래프에 나와 있는 시간 복잡도의 성능을 비교하면 다음과 같다.
- 상수함수 < 로그함수 < 선형함수 < 다항함수 < 지수함수
시간 복잡도를 구하는 요령
- 하나의 루프를 사용하여 단일 요소 집합을 반복하는 경우: O(n)
- 컬렉션의 절반 이상을 반복하는 경우: O(n / 2) -> O(n)
- 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복하는 경우: O(n + m) -> O(n)
- 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우: O(n²)
- 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복하는 경우: O(n * m) -> O(n²)
- 컬렉션 정렬을 사용하는 경우: O(n*log(n))
빅오 표기법 예제
1. O(1) : 스택에서 Push , Pop
2. O(log n) : 이진트리
3. O(n) : for 문
4. O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap sort)
5. O(n²) : 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
6. O(2ⁿ) : 피보나치 수열
- 빅오 표기법이 가장 많이 사용되는 이유는 알고리즘 효율성을 상한선 기준으로 표기하기 때문이다. 최악의 경우를 고려하는데 가장 좋은 표기법으로 알고리즘 효율성은 값이 클수록, 즉 그래프가 위로 향할수록 비효율적임을 의미한다.
Reference
3.빅오 표기법 - https://noahlogs.tistory.com/27
'알고리즘 > 개념' 카테고리의 다른 글
| [알고리즘] 순열과 조합 (0) | 2023.04.11 |
|---|---|
| 정렬 알고리즘(병합 정렬, 힙 정렬) (0) | 2023.04.10 |
| [알고리즘] 기본 정렬 알고리즘(삽입 정렬, 선택 정렬, 버블 정렬) (0) | 2023.04.10 |
| [알고리즘] 퀵 정렬 (0) | 2023.04.10 |
| [알고리즘] 재귀함수(Recursion function), 꼬리재귀함수(Tail call recursion) (0) | 2023.04.09 |
