big-omega
-
복잡도 표기법잡다한 지식 2020. 3. 27. 13:41
알고리즘을 분석하는 방법은 시간 복잡도와 공간 복잡도로 나뉜다.- 시간 복잡도 (time complexity) : 알고리즘이 완료되는데까지 소요되는 시간- 공간 복잡도 (space complexity) : 알고리즘이 완료되는데까지 필요한 메모리 공간 이러한 복잡도의 표기방법으로는 총 3가지가 존재한다.1. 빅오메가(Big-Omega)2. 빅세타(Big-Theta)3. 빅오(Big-O)이 표기법들을 점근적 표기법 즉 대략적인 표기법이라고 한다.n을 알고리즘의 input의 크기라고 할 때.알고리즘의 복잡한 함수를 일일이 나타내지 않고, 알고리즘의 basic operation을 선택해 basic operation의 수를 n에 대한 비례식으로 세우는 것이다. (중요하지 않은 항과 상수 계수를 제거) 각 표기방법..