📌 계산 복잡도
계산 복잡도 이론 (Computatuinal Complexity Theory)은 알고리즘의 자원 소비를 분석하는 방법으로, 계산 문제를 푸는 알고리즘을 복잡도에 따라 분류하는 방법이다.
알고리즘의 효율성을 비교하고 최적의 알고리즘을 선택하는데 도움을 준다.
복잡도 (Complexity) ?
어떤 알고리즘을 실행하기 위해 사용되는 자원을 의미한다.
알고리즘이 특정 입력 크기 (n)에 대해 얼마나 많은 시간을 소요하는지, 또는 얼마나 많은 메모리를 사용하는지를 나타내는 지표이다.
💡 시간 복잡도
시간 복잡도 (Time Complexity)는 알고리즘이 입력 크기에 따라 실행되는데 소요되는 시간을 나타낸다.
- O(1) : 상수 시간 복잡도, 입력 크기와 무관하게 항상 일정한 시간이 소요
- O(log n) : 로그 시간 복잡도
- O(n) : 선형 시간 복잡도, 입력 크기가
n이면 실행 시간도n에 비례 - O(n log n) : 로그 선형 시간 복잡도
- O(n2) : 이차 시간 복잡도
- O(2n) : 지수 시간 복잡도
- O(n!) : 팩토리얼 시간 복잡도
💡 공간 복잡도
공간 복잡도 (Space Complexity)는 알고리즘이 실행될 때 사용되는 메모리의 양을 나타낸다.
알고리즘이 필요로 하는 고정 공간과 가변 공간을 포함한 양을 나타낸다.
- O(1) : 고정 공간 복잡도, 입력 크기에 상관 없이 일정한 메모리만 소요
- O(n) : 선형 공간 복잡도, 입력 크기와 비례하여 메모리를 소요
- O(n2) : 이차 공간 복잡도
📌 점근적 표기법
알고리즘의 성능을 분석하는데 사용되는 수학적 표현이다.
알고리즘의 수행 시간을 표시할 때, 가장 높은 차수의 증가폭에 의해 제일 크게 변화한다.
따라서 제일 높은 차수만을 표시하고 그보다 낮은 차수의 표기는 상대적으로 중요하지 않기 때문에 생략하여 표기한다.
ex)
f(n) = n2 + n + 100 일 때, 가장 높은 차수는 n2
다른 차수들은 가장 높은 차수에 비해 증가폭이 크지 않기 때문에 가장 높은 차수만을 활용하여 표기
=> O(n2)
💡 표기법의 종류
1. 빅-오 표기법 (Big-O Notation)
빅-오 표기법은 상한 표기법으로, 점근적 상한만 알고 있을 때 사용하는 표기법이다.
일반적으로 가장 많이 사용하는 표기법이다.
빅-오 표기법은 다음과 같은 함수의 집합으로 나타낸다.
알고리즘의 최악인 경우 시간 복잡도나 공간 복잡도를 나타낸다.
2. 오메가 표기법 (Big-Omega Notation)
오메가 표기법은 하한 표기법으로, 점근적 하한만 알고 있을 때 사용하는 표기법이다.
오메가 표기법은 다음과 같은 함수의 집합으로 나타낸다.
알고리즘의 최선의 경우 시간 복잡도나 공간 복잡도를 나타낸다.
3. 세타 표기법 (big-Theta Notation)
세타 표기법은 상하한 표기법으로, 상한과 하한을 둘 다 알고 있을 때 사용하는 표기법이다.
세타 표기법은 다음과 같은 함수의 집합으로 나타낸다.
알고리즘의 최악의 경우와 최선의 경우 모두 같은 성능을 가진다는 것을 나타낸다.
Reference
계산 복잡도 이론 - 위키 백과
점근 표기법 - 위키 백과
Complexity Analysis (1) - Computational Complexity (계산 복잡도)
[알고리즘] 계산 복잡도 (시간 복잡도, 공간 복잡도), 빅 오 표기법
점근 표기법(Asymptotic Notation)
알고리즘 이론 2강. 점근적 표기법(Asymptotic Notation)
